Obtaining a powerset of a set in Java

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... :)

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