# Obtaining a powerset of a set in Java

556
June 06, 2017, at 08:47 AM

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>();
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).)

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()) {
return sets;
}
List<T> list = new ArrayList<T>(originalSet);
Set<T> rest = new HashSet<T>(list.subList(1, list.size()));
for (Set<T> set : powerSet(rest)) {
Set<T> newSet = new HashSet<T>();
}
return sets;
}
``````

And a test, given your example input:

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

Actually, I've written code that does what you're asking for in O(1). The question is what you plan to do with the Set next. If you're just going to call `size()` on it, that's O(1), but if you're going to iterate it that's obviously `O(2^n)`.

`contains()` would be `O(n)`, etc.

Do you really need this?

EDIT:

This code is now available in Guava, exposed through the method `Sets.powerSet(set)`.

Here's a solution where I use a generator, the advantage being, the entire power set is never stored at once... So you can iterate over it one-by-one without needing it to be stored in memory. I'd like to think it's a better option... Note the complexity is the same, O(2^n), but the memory requirements are reduced (assuming the garbage collector behaves! ;) )

``````/**
*
*/
package org.mechaevil.util.Algorithms;
import java.util.BitSet;
import java.util.Iterator;
import java.util.Set;
import java.util.TreeSet;
/**
* @author st0le
*
*/
public class PowerSet<E> implements Iterator<Set<E>>,Iterable<Set<E>>{
private E[] arr = null;
private BitSet bset = null;
@SuppressWarnings("unchecked")
public PowerSet(Set<E> set)
{
arr = (E[])set.toArray();
bset = new BitSet(arr.length + 1);
}
@Override
public boolean hasNext() {
return !bset.get(arr.length);
}
@Override
public Set<E> next() {
Set<E> returnSet = new TreeSet<E>();
for(int i = 0; i < arr.length; i++)
{
if(bset.get(i))
}
//increment bset
for(int i = 0; i < bset.size(); i++)
{
if(!bset.get(i))
{
bset.set(i);
break;
}else
bset.clear(i);
}
return returnSet;
}
@Override
public void remove() {
throw new UnsupportedOperationException("Not Supported!");
}
@Override
public Iterator<Set<E>> iterator() {
return this;
}
}
``````

To call it, use this pattern:

``````        Set<Character> set = new TreeSet<Character> ();
for(int i = 0; i < 5; i++)
PowerSet<Character> pset = new PowerSet<Character>(set);
for(Set<Character> s:pset)
{
System.out.println(s);
}
``````

It's from my Project Euler Library... :)

Here is a tutorial describing exactly what you want, including the code. You're correct in that the complexity is O(2^n).

If n < 63, which is a reasonable assumption since you'd run out of memory (unless using an iterator implementation) trying to construct the power set anyway, this is a more concise way to do it. Binary operations are way faster than `Math.pow()` and arrays for masks, but somehow Java users are afraid of them...

``````List<T> list = new ArrayList<T>(originalSet);
int n = list.size();
Set<Set<T>> powerSet = new HashSet<Set<T>>();
for( long i = 0; i < (1 << n); i++) {
Set<T> element = new HashSet<T>();
for( int j = 0; j < n; j++ )
if( (i >> j) % 2 == 1 ) element.add(list.get(j));
}
return powerSet;
``````

I came up with another solution based on @Harry He's ideas. Probably not the most elegant but here it goes as I understand it:

Let's take the classical simple example PowerSet of S P(S) = {{1},{2},{3}}. We know the formula to get the number of subsets is 2^n (7 + empty set). For this example 2^3 = 8 subsets.

In order to find each subset we need to convert 0-7 decimal to binary representation shown in the conversion table below:

If we traverse the table row by row, each row will result in a subset and the values of each subset will come from the enabled bits.

Each column in the Bin Value section corresponds to the index position in the original input Set.

Here my code:

``````public class PowerSet {
/**
* @param args
*/
public static void main(String[] args) {
PowerSet ps = new PowerSet();
Set<Integer> set = new HashSet<Integer>();
for (Set<Integer> s : ps.powerSet(set)) {
System.out.println(s);
}
}
public Set<Set<Integer>> powerSet(Set<Integer> originalSet) {
// Original set size e.g. 3
int size = originalSet.size();
// Number of subsets 2^n, e.g 2^3 = 8
int numberOfSubSets = (int) Math.pow(2, size);
Set<Set<Integer>> sets = new HashSet<Set<Integer>>();
ArrayList<Integer> originalList = new ArrayList<Integer>(originalSet);
for (int i = 0; i < numberOfSubSets; i++) {
// Get binary representation of this index e.g. 010 = 2 for n = 3
//Get sub-set
Set<Integer> set = getSet(bin, originalList));
}
return sets;
}
//Gets a sub-set based on the binary representation. E.g. for 010 where n = 3 it will bring a new Set with value 2
private Set<Integer> getSet(String bin, List<Integer> origValues){
Set<Integer> result = new HashSet<Integer>();
for(int i = bin.length()-1; i >= 0; i--){
//Only get sub-sets where bool flag is on
if(bin.charAt(i) == '1'){
int val = origValues.get(i);
}
}
return result;
}
//Converts an int to Bin and adds left padding to zero's based on size
private String getPaddedBinString(int i, int size) {
String bin = Integer.toBinaryString(i);
bin = String.format("%0" + size + "d", Integer.parseInt(bin));
return bin;
}
}
``````

I was looking for a solution that wasn't as huge as the ones posted here. This targets Java 7, so it will require a handful of pastes for versions 5 and 6.

``````Set<Set<Object>> powerSetofNodes(Set<Object> orig) {
Set<Set<Object>> powerSet = new HashSet<>(),
runSet = new HashSet<>(),
thisSet = new HashSet<>();
while (powerSet.size() < (Math.pow(2, orig.size())-1)) {
if (powerSet.isEmpty()) {
for (Object o : orig) {
Set<Object> s = new TreeSet<>();
}
continue;
}
for (Object o : orig) {
for (Set<Object> s : runSet) {
Set<Object> s2 = new TreeSet<>();
}
}
runSet.clear();
thisSet.clear();
}
return powerSet;
``````

Here's some example code to test:

``````Set<Object> hs = new HashSet<>();
for(Set<Object> s : powerSetofNodes(hs)) {
System.out.println(Arrays.toString(s.toArray()));
}
``````

If you're using Eclipse Collections (formerly GS Collections), you can use the `powerSet()` method on all SetIterables.

``````MutableSet<Integer> set = UnifiedSet.newSetWith(1, 2, 3);
System.out.println("powerSet = " + set.powerSet());
// prints: powerSet = [[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]]
``````

Note: I am a committer for Eclipse Collections.

The following solution is borrowed from my book "Coding Interviews: Questions, Analysis & Solutions":

Some integers in an array are selected that compose a combination. A set of bits is utilized, where each bit stands for an integer in the array. If the i-th character is selected for a combination, the i-th bit is 1; otherwise, it is 0. For instance, three bits are used for combinations of the array [1, 2, 3]. If the first two integers 1 and 2 are selected to compose a combination [1, 2], the corresponding bits are {1, 1, 0}. Similarly, bits corresponding to another combination [1, 3] are {1, 0, 1}. We are able to get all combinations of an array with length n if we can get all possible combinations of n bits.

A number is composed of a set of bits. All possible combinations of n bits correspond to numbers from 1 to 2^n-1. Therefore, each number in the range between 1 and 2^n-1 corresponds to a combination of an array with length n. For example, the number 6 is composed of bits {1, 1, 0}, so the first and second characters are selected in the array [1, 2, 3] to generate the combination [1, 2]. Similarly, the number 5 with bits {1, 0, 1} corresponds to the combination [1, 3].

The Java code to implement this solution looks like below:

``````public static ArrayList<ArrayList<Integer>> powerSet(int[] numbers) {
ArrayList<ArrayList<Integer>> combinations = new ArrayList<ArrayList<Integer>>();
BitSet bits = new BitSet(numbers.length);
do{
}while(increment(bits, numbers.length));
return combinations;
}
private static boolean increment(BitSet bits, int length) {
int index = length - 1;
while(index >= 0 && bits.get(index)) {
bits.clear(index);
--index;
}
if(index < 0)
return false;
bits.set(index);
return true;
}
private static ArrayList<Integer> getCombination(int[] numbers, BitSet bits){
ArrayList<Integer> combination = new ArrayList<Integer>();
for(int i = 0; i < numbers.length; ++i) {
if(bits.get(i))
}
return combination;
}
``````

The method increment increases a number represented in a set of bits. The algorithm clears 1 bits from the rightmost bit until a 0 bit is found. It then sets the rightmost 0 bit to 1. For example, in order to increase the number 5 with bits {1, 0, 1}, it clears 1 bits from the right side and sets the rightmost 0 bit to 1. The bits become {1, 1, 0} for the number 6, which is the result of increasing 5 by 1.

Some of the solutions above suffer when the size of the set is large because they are creating a lot of object garbage to be collected and require copying data. How can we avoid that? We can take advantage of the fact that we know how big the result set size will be (2^n), preallocate an array that big, and just append to the end of it, never copying.

The speedup grows quickly with n. I compared it to João Silva's solution above. On my machine (all measurements approximate), n=13 is 5x faster, n=14 is 7x, n=15 is 12x, n=16 is 25x, n=17 is 75x, n=18 is 140x. So that garbage creation/collection and copying is dominating in what otherwise seem to be similar big-O solutions.

Preallocating the array at the beginning appears to be a win compared to letting it grow dynamically. With n=18, dynamic growing takes about twice as long overall.

``````public static <T> List<List<T>> powerSet(List<T> originalSet) {
// result size will be 2^n, where n=size(originalset)
// good to initialize the array size to avoid dynamic growing
int resultSize = (int) Math.pow(2, originalSet.size());
// resultPowerSet is what we will return
List<List<T>> resultPowerSet = new ArrayList<List<T>>(resultSize);
// Initialize result with the empty set, which powersets contain by definition
// for every item in the original list
for (T itemFromOriginalSet : originalSet) {
// iterate through the existing powerset result
// loop through subset and append to the resultPowerset as we go
// must remember size at the beginning, before we append new elements
int startingResultSize = resultPowerSet.size();
for (int i=0; i<startingResultSize; i++) {
List<T> oldSubset = resultPowerSet.get(i);
// create a new element by adding a new item from the original list
List<T> newSubset = new ArrayList<T>(oldSubset);
// add this element to the result powerset (past startingResultSize)
}
}
return resultPowerSet;
}
``````

Here is an easy iterative O(2^n) solution:

``````public static Set<Set<Integer>> powerSet(List<Integer> intList){
Set<Set<Integer>> result = new HashSet();
for (Integer i : intList){
Set<Set<Integer>> temp = new HashSet();
for(Set<Integer> intSet : result){
intSet = new HashSet(intSet);
}
}
return result;
}
``````
``````import java.util.Set;
Set<Set<Integer>> sets = Sets.powerSet(ImmutableSet.of(1, 2, 3));
``````

If S is a finite set with N elements, then the power set of S contains 2^N elements. The time to simply enumerate the elements of the powerset is 2^N, so `O(2^N)` is a lower bound on the time complexity of (eagerly) constructing the powerset.

Put simply, any computation that involves creating powersets is not going to scale for large values of N. No clever algorithm will help you ... apart from avoiding the need to create the powersets!

One way without recursion is the following: Use a binary mask and make all the possible combinations.

``````public HashSet<HashSet> createPowerSet(Object[] array)
{
HashSet<HashSet> powerSet=new HashSet();
for(int i=0;i<Math.pow(2, array.length);i++)
{
HashSet set=new HashSet();
{
}
}
return powerSet;
}
{
boolean carry=false;
{
carry=true;
}
else
{
{
carry=false;
}
else
break;
}
}
``````

Algorithm:

Input: Set[], set_size 1. Get the size of power set powet_set_size = pow(2, set_size) 2 Loop for counter from 0 to pow_set_size (a) Loop for i = 0 to set_size (i) If ith bit in counter is set Print ith element from set for this subset (b) Print seperator for subsets i.e., newline

``````#include <stdio.h>
#include <math.h>

void printPowerSet(char *set, int set_size)
{
/*set_size of power set of a set with set_size
n is (2**n -1)*/
unsigned int pow_set_size = pow(2, set_size);
int counter, j;

/*Run from counter 000..0 to 111..1*/
for(counter = 0; counter < pow_set_size; counter++)
{
for(j = 0; j < set_size; j++)
{
/* Check if jth bit in the counter is set
If set then pront jth element from set */
if(counter & (1<<j))
printf("%c", set[j]);
}
printf("\n");
}
}

/*Driver program to test printPowerSet*/
int main()
{
char set[] = {'a','b','c'};
printPowerSet(set, 3);

getchar();
return 0;
}``````

This is my recursive solution which can get the power set of any set using Java Generics. Its main idea is to combine the head of the input array with all the possible solutions of the rest of the array as follows.

``````import java.util.LinkedHashSet;
import java.util.Set;
public class SetUtil {
private static<T>  Set<Set<T>> combine(T head, Set<Set<T>> set) {
for (Set<T> currentSet : set) {
}
return all;
}
//Assuming that T[] is an array with no repeated elements ...
public static<T> Set<Set<T>> powerSet(T[] input) {
if (input.length == 0) {
return emptySet;
}
T[] newInputSet = (T[]) new Object[input.length - 1];
for (int i = 1; i < input.length; ++i) {
newInputSet[i - 1] = input[i];
}
return all;
}
public static void main(String[] args) {
Set<Set<Integer>> set = SetUtil.powerSet(new Integer[] {1, 2, 3, 4, 5, 6});
System.out.println(set);
}
}
``````

This will output:

``````[[1, 2, 3, 4, 5, 6], [1, 2, 3, 4, 5], [1, 2, 3, 4, 6], [1, 2, 3, 4], [1, 2, 3, 5, 6], [1, 2, 3, 5], [1, 2, 3, 6], [1, 2, 3], [1, 2, 4, 5, 6], [1, 2, 4, 5], [1, 2, 4, 6], [1, 2, 4], [1, 2, 5, 6], [1, 2, 5], [1, 2, 6], [1, 2], [1, 3, 4, 5, 6], [1, 3, 4, 5], [1, 3, 4, 6], [1, 3, 4], [1, 3, 5, 6], [1, 3, 5], [1, 3, 6], [1, 3], [1, 4, 5, 6], [1, 4, 5], [1, 4, 6], [1, 4], [1, 5, 6], [1, 5], [1, 6], [1], [2, 3, 4, 5, 6], [2, 3, 4, 5], [2, 3, 4, 6], [2, 3, 4], [2, 3, 5, 6], [2, 3, 5], [2, 3, 6], [2, 3], [2, 4, 5, 6], [2, 4, 5], [2, 4, 6], [2, 4], [2, 5, 6], [2, 5], [2, 6], [2], [3, 4, 5, 6], [3, 4, 5], [3, 4, 6], [3, 4], [3, 5, 6], [3, 5], [3, 6], [3], [4, 5, 6], [4, 5], [4, 6], [4], [5, 6], [5], [6], []]
``````

This is my approach with lambdas.

``````public static <T> Set<Set<T>> powerSet(T[] set) {
return IntStream
.range(0, (int) Math.pow(2, set.length))
.parallel() //performance improvement
.mapToObj(e -> IntStream.range(0, set.length).filter(i -> (e & (0b1 << i)) != 0).mapToObj(i -> set[i]).collect(Collectors.toSet()))
.map(Function.identity())
.collect(Collectors.toSet());
}
``````

Or in parallel (see parallel() comment):

Size of input set: 18

Logical processors: 8 à 3.4GHz

Performance improvement: 30%

``````// input: S
// output: P
// S = [1,2]
// P = [], [1], [2], [1,2]
public static void main(String[] args) {
String input = args[0];
String[] S = input.split(",");
String[] P = getPowerSet(S);
if (P.length == Math.pow(2, S.length)) {
for (String s : P) {
System.out.print("[" + s + "],");
}
} else {
System.out.println("Results are incorrect");
}
}
private static String[] getPowerSet(String[] s) {
if (s.length == 1) {
return new String[] { "", s[0] };
} else {
String[] subP1 = getPowerSet(Arrays.copyOfRange(s, 1, s.length));
String[] subP2 = new String[subP1.length];
for (int i = 0; i < subP1.length; i++) {
subP2[i] = s[0] + subP1[i];
}
String[] P = new String[subP1.length + subP2.length];
System.arraycopy(subP1, 0, P, 0, subP1.length);
System.arraycopy(subP2, 0, P, subP1.length, subP2.length);
return P;
}
}
``````

I recently had to use something like this, but needed the smallest sublists (with 1 element, then 2 elements, ...) first. I did not want to include the empty nor the whole list. Also, I did not need a list of all the sublists returned, I just needed to do some stuff with each.

Wanted to do this without recursion, and came up with the following (with the "doing stuff" abstracted into a functional interface):

``````@FunctionalInterface interface ListHandler<T> {
void handle(List<T> list);
}

public static <T> void forAllSubLists(final List<T> list, ListHandler handler) {
int     ll = list.size();   // Length of original list
int     ci[] = new int[ll]; // Array for list indices
List<T> sub = new ArrayList<>(ll);  // The sublist
List<T> uml = Collections.unmodifiableList(sub);    // For passing to handler
for (int gl = 1, gm; gl <= ll; gl++) {  // Subgroup length 1 .. n-1
gm = 0; ci[0] = -1; sub.add(null);  // Some inits, and ensure sublist is at least gl items long
do {
ci[gm]++;                       // Get the next item for this member
if (ci[gm] > ll - gl + gm) {    // Exhausted all possibilities for this position
gm--; continue;         // Continue with the next value for the previous member
}
sub.set(gm, list.get(ci[gm]));  // Set the corresponding member in the sublist
if (gm == gl - 1) {             // Ok, a sublist with length gl
handler.handle(uml);    // Handle it
} else {
ci[gm + 1] = ci[gm];    // Starting value for next member is this
gm++;                   // Continue with the next member
}
} while (gm >= 0);  // Finished cycling through all possibilities
}   // Next subgroup length
}
``````

In this way, it's also easy to limit it to sublists of specific lengths.

Another sample implementation:

`````` public static void main(String args[])
{
int[] arr = new int[]{1,2,3,4};
// Assuming that number of sets are in integer range
int totalSets = (int)Math.pow(2,arr.length);
for(int i=0;i<totalSets;i++)
{
String binaryRep = Integer.toBinaryString(i);
for(int j=0;j<binaryRep.length();j++)
{
int index=binaryRep.length()-1-j;
if(binaryRep.charAt(index)=='1')
System.out.print(arr[j] +" ");
}
System.out.println();
}
}
``````
``````public class PowerSet {
public static List<HashSet<Integer>> powerset(int[] a) {
int n = a.length;
for (int i = 0; i < 1 << n; i++) {
HashSet<Integer> set = new HashSet<Integer>();
for (int j = 0; j < n; j++) {
if ((1 << j & i) > 0)
}
}
return sets;
}
public static void main(String[] args) {
List<HashSet<Integer>> sets = PowerSet.powerset(new int[]{ 1, 2, 3 });
for (HashSet<Integer> set : sets) {
for (int i : set)
System.out.print(i);
System.out.println();
}
}
}
``````

Yet another solution - with java8+ streaming api It is lazy and ordered so it returns correct subsets when it is used with "limit()".

`````` public long bitRangeMin(int size, int bitCount){
BitSet bs = new BitSet(size);
bs.set(0, bitCount);
return bs.toLongArray()[0];
}
public long bitRangeMax(int size, int bitCount){
BitSet bs = BitSet.valueOf(new long[]{0});
bs.set(size - bitCount, size);
return bs.toLongArray()[0];
}
public <T> Stream<List<T>> powerSet(Collection<T> data)
{
Stream<BitSet> head = LongStream.of(0).mapToObj( i -> BitSet.valueOf(new long[]{i}));
Stream<BitSet> tail = IntStream.rangeClosed(1, list.size())
.boxed()
.flatMap( v1 -> LongStream.rangeClosed( bitRangeMin(list.size(), v1), bitRangeMax(list.size(), v1))
.mapToObj(v2 -> BitSet.valueOf(new long[]{v2}))
.filter( bs -> bs.cardinality() == v1));
.map( bs -> bs
.stream()
.mapToObj(list::get)
.collect(Collectors.toList()));
}
``````

And the client code is

``````@Test
public void testPowerSetOfGivenCollection(){
for(char i = 'a'; i < 'a'+5; i++ ){
}
powerSet(data)
.limit(9)
.forEach(System.out::print);
}
``````

/* Prints : [][a][b][c][d][e][a, b][a, c][b, c] */

We could write the power set with or without using recursion. Here is an attempt without recursion:

``````public List<List<Integer>> getPowerSet(List<Integer> set) {
List<List<Integer>> powerSet = new ArrayList<List<Integer>>();
int max = 1 << set.size();
for(int i=0; i < max; i++) {
List<Integer> subSet = getSubSet(i, set);
}
return powerSet;
}
private List<Integer> getSubSet(int p, List<Integer> set) {
List<Integer> subSet = new ArrayList<Integer>();
int position = 0;
for(int i=p; i > 0; i >>= 1) {
if((i & 1) == 1) {
}
position++;
}
return subSet;
}
``````
POPULAR ONLINE

### How to disable user moving Progress Bar Javafx

Oddly enough individuals are allowed to go to the edges of my progress bar in the bottom right of this picture and move the progress bar left and right:

831

### Convert hours, mins, secs String to hours

I want to convert a time in the below format into hours

659

### Is it possible to use channels and buffers (java.nio) to read/write types of objects I created from/to a file?

I would like to know if it is possible to use channels and buffers (from javanio) to read/write types of objects I created from/to a file ?

550

### Java database simulator to test query, How to write? [on hold]

In this problem, you will be given some table informationEvery table has a unique name and you can assume the name of each column of these tables are unique too

480