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).

Answer 2

I would use divide and conquer for this:

Set powerSet(Set set) {
  return merge(powerSet(Set leftHalf), powerSet(Set rightHalf));
}

merge(Set leftHalf, Set rightHalf) {
  return union(leftHalf, rightHalf, allPairwiseCombinations(leftHalf, rightHalf));
}

That way, you immediately see that the number of solutions is 2^|originalSet| - that's why it is called the "power set". In your case, this would be 2^9, so there should not be an out of memory error on a 1GB machine. I guess you have some error in your algorithm.

Answer 3

a little scheme solution

(define (power_set_iter set)
  (let loop ((res '(())) 
             (s    set ))
    (if (empty? s)
        res
        (loop (append (map (lambda (i) 
                             (cons (car s) i)) 
                           res) 
                      res) 
              (cdr s)))))

Or in R5RS Scheme, more space efficient version

(define (pset s)
  (do ((r '(()))
       (s s (cdr s)))
      ((null? s) r)
    (for-each 
      (lambda (i) 
        (set! r (cons (cons (car s) i) 
                      r)))
      (reverse r))))