What algorithm can calculate the power set of a given set?
I would like to efficiently generate a unique list of combinations of numbers based on a starting list of numbers.
example start list = [1,2,3,4,5]
but the algorithm should work for [1,2,3...n]
result =
[1],[2],[3],[4],[5]
[1,2],[1,3],[1,4],[1,5]
[1,2,3],[1,2,4],[1,2,5]
[1,3,4],[1,3,5],[1,4,5]
[2,3],[2,4],[2,5]
[2,3,4],[2,3,5]
[3,4],[3,5]
[3,4,5]
[4,5]
Note. I don't want duplicate combinations, although I could live with them, eg in the above example I don't really need the combination [1,3,2] because it already present as [1,2,3]
Just count 0
to 2^n - 1
and print the numbers according to the binary representation of your count. a 1
means you print that number and a 0
means you don't. Example:
set is {1, 2, 3, 4, 5}
count from 0 to 31:
count = 00000 => print {}
count = 00001 => print {1} (or 5, the order in which you do it really shouldn't matter)
count = 00010 => print {2}
00011 => print {1, 2}
00100 => print {3}
00101 => print {1, 3}
00110 => print {2, 3}
00111 => print {1, 2, 3}
...
11111 => print {1, 2, 3, 4, 5}
There is a name for what you're asking. It's called the power set.
Googling for "power set algorithm" led me to this recursive solution.
Ruby Algorithm
def powerset!(set)
return [set] if set.empty?
p = set.pop
subset = powerset!(set)
subset | subset.map { |x| x | [p] }
end
Power Set Intuition
If S = (a, b, c) then the powerset(S) is the set of all subsets powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
The first "trick" is to try to define recursively.
What would be a stop state?
S = () has what powerset(S)?
How get to it?
Reduce set by one element
Consider taking an element out - in the above example, take out {c}
S = (a,b) then powerset(S) = {(), (a), (b), (a,b)}
What is missing?
powerset(S) = {(c), (a,c), (b,c), (a,b,c)}
hmmm
Notice any similarities? Look again...
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)}
take any element out
powerset(S) = {(), (a), (b), (c), (a,b), (a,c), (b,c), (a,b,c)} is
powerset(S - {c}) = {(), (a), (b), (a,b)} unioned with
{c} U powerset(S - {c}) = { (c), (a,c), (b,c), (a,b,c)}
powerset(S) = powerset(S - {ei}) U ({ei} U powerset(S - {ei}))
where ei is an element of S (a singleton)
Pseudo-algorithm
- Is the set passed empty? Done (Note that power set of {} is {{}})
- If not, take an element out
- recursively call method on the remainder of the set
- return the set composed of the Union of
- the powerset of the set without the element (from the recursive call)
- this same set (i.e., 2.1) but with each element therein unioned with the element initially taken out
def power(a)
(0..a.size).map {|x| a.combination(x).to_a}.flatten(1)
end