Memory efficient power set algorithm

Question

Trying to calculate all the subsets (power set) of the 9-letter string 'ABCDEFGHI'.

Using standard recursive methods, my machine hits out of memory (1GB) error before completing. I have no more physical memory.

How can this be done better? Language is no issue and results sent to the standard output is fine as well - it does not need to be held all in memory before outputting.

Answer 1

There is a trivial bijective mapping from the power set of X = {A,B,C,D,E,F,G,H,I} to the set of numbers between 0 and 2^|X| = 2^9:

Ø maps to 000000000 (base 2)

{A} maps to 100000000 (base 2)

{B} maps to 010000000 (base 2)

{C} maps to 001000000 (base 2)

...

{I} maps to 000000001 (base 2)

{A,B} maps to 110000000 (base 2)

{A,C} maps to 101000000 (base 2)

...

{A,B,C,D,E,F,G,H,I} maps to 111111111 (base 2)

You can use this observation to create the power set like this (pseudo-code):

Set powerset = new Set();
for(int i between 0 and 2^9)
{
  Set subset = new Set();
  for each enabled bit in i add the corresponding letter to subset
  add subset to powerset
}

In this way you avoid any recursion (and, depending on what you need the powerset for, you may even be able to "generate" the powerset without allocating many data structures - for example, if you just need to print out the power set).