4
$\begingroup$

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?

  • 0
    @ThomasAndrews It's not specifically applicable to problem 1, I'm trying for$a$general solution where I can pass `f(range, multiples)` such as `f(1000,[3, 5])` or `f(1000000, [2, 3, 6, 100, 101])`.2011-12-16

1 Answers 1

14

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.

  • 3
    @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$).2011-12-16