# For a set such as $\{n_1, n_2,\ldots n_k\}$, how can I create all combinations?

Lets say I have a set of $\{a, b, c, d\}$, is there a means by which I can generate a set that contains all permutations of sets, such as... $$\{ ab, ac, ad, bc, bd, cd, abc, abd, acd, bcd, abcd \}$$

I'm unsure what the name for this computation is, or a means to do so that are not a manual process. I'm able to write computer code that does this using nested loops, but that seems to be an inelegant solution to the problem. Perhaps there's a matrix multiplication I can use?

-
Why are you skipping the combinations with one terms, and only the combinations with one term? –  Arturo Magidin Dec 16 '11 at 19:25
@ArturoMagidin I'm solving the project Euler problem 1 ( projecteuler.net/problem=1 ). I am calculating an arithmetic progression, but over-lapping multiples need to be excluded from the sum (ie, 3-series and 5 series needs to subtract the 15 series). I'm solving the problem generally (a function that takes multiples as an argument) rather than specifically the one they're asking for. I think I see how to use the full set to do more powerful things than I had originally thought of. –  Incognito Dec 16 '11 at 19:39
Seems like a heavy-handed (and unimaginative) way of doing it. It's much simpler to add the multiples of $3$, the multiples of $5$, and subtract the multiples of $15$. –  Arturo Magidin Dec 16 '11 at 19:40
@ArturoMagidin What I really want is to do this jsfiddle.net/BDG/wDyN7/4 by doing it more like this jsfiddle.net/BDG/zYt7K/2 . –  Incognito Dec 16 '11 at 19:43
Counting common multiples of $a$ and $b$ is a lot simpler than that: the common multiples of $a$ and $b$ are precisely the multiples of the least common multiple. The least common multiple of $a$ and $b$ is $ab/\gcd(a,b)$. And $\gcd(a,b)$ can be computed easily using the Euclidean algorithm. –  Arturo Magidin Dec 16 '11 at 19:48

## 1 Answer

You can first construct the power set; there is a simple way of doing this by just looping through the numbers $1$ through $2^k-1$ (in your case, $1$ through $15$); take the number $m$, write in binary, and take the subset of those $n_i$ for which the $i$th bit of $m$ is $1$. Thus, with $\{a,b,c,d\}$, you would have:

 1: 0001   -> {d}
2: 0010   -> {c}
3: 0011   -> {c,d}
4: 0100   -> {b}
5: 0101   -> {b,d}
6: 0110   -> {b,c}
7: 0111   -> {b,c,d}
8: 1000   -> {a}
9: 1001   -> {a,d}
10: 1010   -> {a,c}
11: 1011   -> {a,c,d}
12: 1100   -> {a,b}
13: 1101   -> {a,b,d}
14: 1110   -> {a,b,c}
15: 1111   -> {a,b,c,d}


Once you have the subset, just drop the parentheses and the commas.

-
Is there a means to generate this without the single-length values at 1, 2, 4, and 8? –  Incognito Dec 16 '11 at 19:12
@Incognito: Sure: add the bits in the number; if the total is $1$, skip it. If the total is greater than 1, list it. (Alternatively, skip the terms where the index is a power of $2$). –  Arturo Magidin Dec 16 '11 at 19:24