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?

  • 1
    Why are you skipping the combinations with one terms, and only the combinations with one term?2011-12-16
  • 0
    @ArturoMagidin I'm solving the project Euler problem 1 ( http://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.2011-12-16
  • 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$.2011-12-16
  • 0
    @ArturoMagidin What I really want is to do this http://jsfiddle.net/BDG/wDyN7/4/ by doing it more like this http://jsfiddle.net/BDG/zYt7K/2/ .2011-12-16
  • 0
    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.2011-12-16
  • 0
    I can't even see how to use this problem so solve Project Euler 1, which, as Arturo says, has a much easier solution which scales much more nicely to, for example, the sum of multiples of $3$ or $5$ between $1,0000,0000$ and $10,000,000$.2011-12-16
  • 0
    @ArturoMagidin Thank you for all the help, I'm going to study the Euclidean Algorithm.2011-12-16
  • 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.

  • 0
    Is there a means to generate this without the single-length values at 1, 2, 4, and 8?2011-12-16
  • 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