CODEWITHSUNDEEP
javaalgorithmmath
rejeep
rejeep

Reputation: 649

Algorithm for calculating the power set

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);
  }
}

Upvotes: 3

Views: 12808

Answers (3)

Jo&#227;o Silva
Jo&#227;o Silva

Reputation: 91319

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.

Upvotes: 3

Michiel Rop
Michiel Rop

Reputation: 9

public final static Set<Set<Character>> powerSet(Set<Character> s){
    Set<Set<Character>> result = new HashSet<Set<Character>>();
    result.add(s);
    for (Character c:s){
        Set<Character> subSet = new HashSet<Character>(s);
        subSet.remove(c);
        result.addAll(powerSet(subSet));
    }
    return result;
}

Upvotes: 0

Richie Cotton
Richie Cotton

Reputation: 121077

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.

Upvotes: 3

Related Questions