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?

$\endgroup$
8
  • 1
    $\begingroup$ Why are you skipping the combinations with one terms, and only the combinations with one term? $\endgroup$
    – Arturo Magidin
    Dec 16 '11 at 19:25
  • $\begingroup$ @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. $\endgroup$
    – Incognito
    Dec 16 '11 at 19:39
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Arturo Magidin
    Dec 16 '11 at 19:40
  • $\begingroup$ @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 . $\endgroup$
    – Incognito
    Dec 16 '11 at 19:43
  • $\begingroup$ 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. $\endgroup$
    – Arturo Magidin
    Dec 16 '11 at 19:48
14
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is there a means to generate this without the single-length values at 1, 2, 4, and 8? $\endgroup$
    – Incognito
    Dec 16 '11 at 19:12
  • 3
    $\begingroup$ @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$). $\endgroup$
    – Arturo Magidin
    Dec 16 '11 at 19:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.