Algorithm for calculating the power set

Question

Hi!

I just discovered an algorithm for finding the power set. I googled after solutions, but found none that worked any good, so I figured out one myself. But I wonder what algorithm it is, because I cannot find it on the net or in any books. I mean, does it have a name? I hardly think I'm the inventor of it. But compared to the algorithms I found on some sites for calculating the power set, I think mine is far better and wonder why no one uses it?

This is the algorithm:

R <- []
L <- [ e1, e2 ... en ]
c <- 0
function: powerSet(L, c)
  R <- R union L
  for e in L starting at c
    powerSet(L\{e}, c)
  end
  return R
end

And here it is implemented in Java:

public static void powerSet(List<String> list, int count)
{
  result.add(list);

  for(int i = count; i < list.size(); i++)
  {
    List<String> temp = new ArrayList<String>(list);
    temp.remove(i);

    powerSet(temp, i);
  }
}

Does anyone recognize it, or am I the inventor? :)

Johan Andersson

Answer 1

Mainly for two reasons:

1. It uses global variables;
2. It is recursive, although this doesn't really matter much because it's an O(2^n) algorithm.

Answer 2

Take a look at the Rosetta Code Power Set page. There are a few implementations of recursive solutions there (including a Java one). In general though, a recursive solution implies a crazily large call stack which slows things down.