Algorithm for calculating the power set
12,717
Solution 1
Mainly for two reasons:
- It uses global variables;
- It is recursive, although this doesn't really matter much because it's an
O(2^n)
algorithm.
Solution 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.
Author by
rejeep
Updated on June 04, 2022Comments
-
rejeep almost 2 years
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? 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); } }