How to find the power set?

[DaveNo1]

I ran into the following issue on several euler problems; I was not so sure if power set is correct, in german it is "Potenzmenge".

We have a set of dynamic length and want to get all subsets with length k. Is there an elegant way to find them without using k for loops on the set (which is the "ugly" way I found). The number of these subsets can be found using binomial coefficients, but we don't search the number but the subsets themselves.

And in addition: Is there a way to get subsets of length k, where k may be changed in runtime?

[DNS]

Try to read here:
http://reference.wolfram.com/mathematic ... bsets.html

[DaveNo1]

That is exactly the problem, now the thing is: How to implement this in java or c++? On the linked page I found a manual how to use built in mathematica function, but not the way the function works.

[hk]

If you have a set with n elements the total number of subsets is 2ⁿ.
So the numbers 0..2ⁿ-1 can be used to represent all subsets.
Suppose you have the set {a,b,c} you have the numbers 0..7
Those numbers with the lowest bit set represent subsets containing a.
Those numbers with the second bit set represent subsets containing b.
Those numbers with the third bit set represent subsets containing c.

[ed_r]

Dave, if you've run into this issue on several PE problems then I think the best action for you would be to solve those problems (however inefficiently) and then look at the solution forum to see what other people did. That's how PE is set up to help you learn: you battle through with a home-made solution, then learn from the clever tricks that others used.

[pjt33]

There's an efficient way to do it for sets not larger than 63 (64 if you have unsigned longs in your language). HAKMEM #169. Alternatively, see Knuth's preprint of TAoCP, Vol 4, Fascicle 1a, or check out my code in the discussion fora for problem 215*.

*Or for another problem, but I've edited that one out because it would give away too much of my solution.

[btilly]

I would use recursion to visit every solution, and in the base case in the recursive function you process that set. That avoids having to generate the entire set of sets in memory at once.

[DaveNo1]

Even if it is not the most performant solution and knuth has found something faster, the binary trick is perfect for my claims! Thanks for your help.

And no, this was not about Problem 215, where i used another approach.