Obtaining a powerset of a set in Java

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

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))                returnSet.add(arr[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++)            set.add((char) (i + 'A'));        PowerSet<Character> pset = new PowerSet<Character>(set);        for(Set<Character> s:pset)        {            System.out.println(s);        }

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