Obtaining a powerset of a set in Java

Question

The powerset of {1, 2, 3} is:

{{}, {2}, {3}, {2, 3}, {1, 2}, {1, 3}, {1, 2, 3}, {1}}

Let's say I have a Set in Java:

Set<Integer> mySet = new HashSet<Integer>(); mySet.add(1); mySet.add(2); mySet.add(3); Set<Set<Integer>> powerSet = getPowerset(mySet); 

How do I write the function getPowerset, with the best possible order of complexity? (I think it might be O(2^n).)

Answer 1

Yes, it is O(2^n) indeed, since you need to generate, well, 2^n possible combinations. Here's a working implementation, using generics and sets:

public static <T> Set<Set<T>> powerSet(Set<T> originalSet) {     Set<Set<T>> sets = new HashSet<Set<T>>();     if (originalSet.isEmpty()) {         sets.add(new HashSet<T>());         return sets;     }     List<T> list = new ArrayList<T>(originalSet);     T head = list.get(0);     Set<T> rest = new HashSet<T>(list.subList(1, list.size()));      for (Set<T> set : powerSet(rest)) {         Set<T> newSet = new HashSet<T>();         newSet.add(head);         newSet.addAll(set);         sets.add(newSet);         sets.add(set);     }            return sets; }   

And a test, given your example input:

 Set<Integer> mySet = new HashSet<Integer>();  mySet.add(1);  mySet.add(2);  mySet.add(3);  for (Set<Integer> s : SetUtils.powerSet(mySet)) {      System.out.println(s);  }