Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
1  
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
1  
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
show 3 more comments

1 Answer

up vote 12 down vote accepted

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.

share|improve this answer
    
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
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$). –  Arturo Magidin Dec 16 '11 at 19:24
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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