What algorithm can calculate the power set of a given set?

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 - {e_i}) U ({e_i} U powerset(S - {e_i}))

where e_i is an element of S (a singleton)

Pseudo-algorithm

1. Is the set passed empty? Done (Note that power set of {} is {{}})
2. If not, take an element out
   • recursively call method on the remainder of the set
   • return the set composed of the Union of
     1. the powerset of the set without the element (from the recursive call)
     2. this same set (i.e., 2.1) but with each element therein unioned with the element initially taken out