Java - Power Set construction, ordered by set size, lazy

Question

I need to construct the power sets of a set, lazily, by smallest size first. I have a working class+algorithm (see below), but I feel like perhaps it's crazy, because it seems waaaay too elaborate.

I am looking for alternatives; any suggestions? If some of the collections look unfamiliar, they are from the Google Collections library, but the naming convention should make their properties pretty self-explanatory.

import java.util.*;

import com.google.common.base.Function;
import com.google.common.collect.*;

public class PowerSetBuilder<Type> extends ForwardingMap<Type,PowerSetBuilder<Type>> {

 private final ImmutableMap<Type,PowerSetBuilder<Type>> delegate;
 @Override protected ImmutableMap<Type, PowerSetBuilder<Type>> delegate() { return delegate; }
 private final int depth;

 public PowerSetBuilder(ImmutableSet<Type> set) {
  depth = set.size();
  ImmutableMap.Builder<Type, PowerSetBuilder<Type>> builder = ImmutableMap.builder();
  Set<Type> local = Sets.newLinkedHashSet(set);
  Type key;
  for (Iterator<Type> iter = local.iterator(); iter.hasNext(); ) {
   key = iter.next();
   iter.remove();
   builder.put(key, new PowerSetBuilder<Type>(ImmutableSet.copyOf(local)));
  }
  delegate = builder.build();
}

private ImmutableSetMultimap<Integer,ImmutableSet<Type>> powerSets;
private ImmutableSet<ImmutableSet<Type>> powerSet;

public ImmutableSet<ImmutableSet<Type>> powerSet() {
 if (powerSet == null) powerSet = getAllPowers();
 return powerSet;
}

private ImmutableSet<ImmutableSet<Type>> getAllPowers() {
 ImmutableSet.Builder<ImmutableSet<Type>> builder = ImmutableSet.builder();
 for (int i=0;i<=depth;i++) builder.addAll(setsOfSize(i));
 return builder.build();
}

public ImmutableSet<ImmutableSet<Type>> setsOfSize(int size) {
 if (powerSets == null) {
  powerSets = ImmutableSetMultimap.of();
 }
 if (!powerSets.containsKey(size)) {
  ImmutableSetMultimap.Builder<Integer, ImmutableSet<Type>> builder = ImmutableSetMultimap.builder();
  builder.putAll(powerSets);
  builder.putAll(size, makeSetSize(size));
  powerSets = builder.build();
 }
 return powerSets.get(size);
}

private ImmutableSet<ImmutableSet<Type>> makeSetSize(int size) {
 if (size == 0) return ImmutableSet.of(ImmutableSet.<Type>of());
 if (size == 1) return ImmutableSet.copyOf(Iterables.transform(keySet(), singleton)); 

 ImmutableSet.Builder<ImmutableSet<Type>> builder = ImmutableSet.builder();
 int check = 0;
 Type key;
 for (Iterator<Type> keyIter = keySet().iterator(); keyIter.hasNext() && check < depth+1-size; check++) {
  key = keyIter.next();
  builder.addAll(Iterables.transform(get(key).makeSetSize(size-1), prepend(key)));
 }
 return builder.build();
}

private Function<Type,ImmutableSet<Type>> singleton = new Function<Type,ImmutableSet<Type>>() {
 @Override public ImmutableSet<Type> apply(Type element) { return ImmutableSet.of(element); }
};

private Function<ImmutableSet<Type>,ImmutableSet<Type>> prepend(final Type add) {
 return new Function<ImmutableSet<Type>,ImmutableSet<Type>>(){
  @Override public ImmutableSet<Type> apply(ImmutableSet<Type> to) {
   return ImmutableSet.<Type>builder()
    .add(add)
    .addAll(to)
    .build();
  }};
}

}

Answer 1

This seems more readable to me, but you might want to polish up the array manipulations

public class PowerSetIterator<T> implements Iterator<Set<T>>  {

private final List<T> elements;

private final int size;

private int[] currentConfig;

public PowerSetIterator(Set<T> set) {
    if (set==null) {
        throw new NullPointerException();
    }
    elements = Collections.unmodifiableList(new ArrayList<T>(set));
    size = elements.size();
    currentConfig = new int[]{elements.size()};
}

public boolean hasNext() {
    return currentConfig != null;
}

public Set<T> next() {
    if (!hasNext()) {
        throw new NoSuchElementException();
    }



    Set<T> c = config();
    nextConfig();
    return c;
}

private Set<T> config() {
    Set<T> set = new HashSet<T>();
    for (int i=0;i<currentConfig.length-1;i++) {
        set.add(elements.get(currentConfig[i]));
    }
    return set;
}

private void nextConfig() {
    int length = currentConfig.length;
    if (length==size+1) {
        currentConfig = null;
        return;
    }
    if (currentConfig[0]==currentConfig[length -1]-length+1) {
        currentConfig = new int[currentConfig.length+1];
        for (int i=0;i<length;i++) {
            currentConfig[i] = i;
        }
        currentConfig[currentConfig.length-1] = size;
        return;
    }
    for (int i=length-2;i>=0;i--) {
        if (currentConfig[i]+1<currentConfig[i+1]) {
            int nV = currentConfig[i];
            for (int j=i;j<(length-1);j++) {
                currentConfig[j] = ++nV;
            }
            return;
        }
    }

}

public void remove() {
    throw new UnsupportedOperationException();
}

public static void main(String[] args) {
    for (Iterator<Set<Integer>> it = new PowerSetIterator<Integer>(new HashSet<Integer>(Arrays.asList(1, 2, 3,4,5,6)));it.hasNext();) {
        System.out.println(it.next());
    }

}}