Skip to content

Instantly share code, notes, and snippets.

@ylegall
Created November 6, 2013 19:14
Show Gist options
  • Save ylegall/7342338 to your computer and use it in GitHub Desktop.
Save ylegall/7342338 to your computer and use it in GitHub Desktop.
get the powerset of a set
import java.util.Arrays;
import java.util.HashSet;
import java.util.Iterator;
import java.util.Set;
public class Powerset {
static Set<Set<Integer>> powerSet(Set<Integer> s) {
Set<Set<Integer>> ps = new HashSet<Set<Integer>>();
powerSet(s, new HashSet<Integer>(), ps);
return ps;
}
static void powerSet(Set<Integer> s, Set<Integer> accum, Set<Set<Integer>> ps) {
if (s.isEmpty()) {
ps.add(new HashSet<Integer>(accum));
} else {
Iterator<Integer> it = s.iterator();
int i = it.next();
it.remove();
accum.add(i);
powerSet(new HashSet<Integer>(s), new HashSet<Integer>(accum), ps);
accum.remove(i);
powerSet(new HashSet<Integer>(s), new HashSet<Integer>(accum), ps);
}
}
public static void main(String[] args) {
System.out.println(powerSet(new HashSet<Integer>(Arrays.asList(1,2,3))));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment