生成功率集的所有元素

Question

功率集只是给定集的所有子集的集合。它包括所有子集（空集）。 众所周知，这个集合中有2^N个元素，其中N是原始集合中元素的个数。

要构建的功率设定，下面的事情可以使用：

创建一个循环，它迭代的所有整数从0直到2^N-1 继续到二进制表示对于每个整数 每个二进制表示为一组N比特的（对于较少的数字，添加前导零）。 如果某个集合成员包含在当前子集中，则每个位都对应。

import java.util.NoSuchElementException; 
import java.util.BitSet; 
import java.util.Iterator; 
import java.util.Set; 
import java.util.TreeSet; 


public class PowerSet<E> implements Iterator<Set<E>>, Iterable<Set<E>> { 
    private final E[] ary; 
    private final int subsets; 
    private int i; 

    public PowerSet(Set<E> set) { 
     ary = (E[])set.toArray(); 
     subsets = (int)Math.pow(2, ary.length) - 1; 
    } 

    public Iterator<Set<E>> iterator() { 
     return this; 
    } 

    @Override 
    public void remove() { 
     throw new UnsupportedOperationException("Cannot remove()!"); 
    } 

    @Override 
    public boolean hasNext() { 
     return i++ < subsets; 
    } 

    @Override 
    public Set<E> next() { 
     if (!hasNext()) { 
      throw new NoSuchElementException(); 
     } 
     Set<E> subset = new TreeSet<E>(); 
     BitSet bitSet = BitSet.valueOf(new long[] { i }); 
     if (bitSet.cardinality() == 0) { 
      return subset; 
     } 
     for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) { 
      subset.add(ary[e]); 
     } 

     return subset; 
    } 

    // Unit Test 
    public static void main(String[] args) { 
     Set<Integer> numbers = new TreeSet<Integer>(); 
     for (int i = 1; i < 4; i++) { 
      numbers.add(i); 
     } 
     PowerSet<Integer> pSet = new PowerSet<Integer>(numbers); 
     for (Set<Integer> subset : pSet) { 
      System.out.println(subset); 
     } 
    } 
} 

我得到的输出是：

[2] 
[3] 
[2, 3] 
java.util.NoSuchElementException 
    at PowerSet.next(PowerSet.java:47) 
    at PowerSet.next(PowerSet.java:20) 
    at PowerSet.main(PowerSet.java:67) 
    at sun.reflect.NativeMethodAccessorImpl.invoke0(Native Method) 
    at sun.reflect.NativeMethodAccessorImpl.invoke(NativeMethodAccessorImpl.java:57) 
    at sun.reflect.DelegatingMethodAccessorImpl.invoke(DelegatingMethodAccessorImpl.java:43) 
    at java.lang.reflect.Method.invoke(Method.java:606) 
    at edu.rice.cs.drjava.model.compiler.JavacCompiler.runCommand(JavacCompiler.java:272) 

所以，问题是：

1. 我得到了让所有的元素（调试显示我下只要求甚至我的）。
2. 不应抛出异常。

Answer 1

问题出在您的hasNext。那里有i++ < subsets。会发生什么情况是因为hasNext从next()被调用一次，并在迭代for (Set<Integer> subset : pSet)期间再次调用i每次2。你可以看到这一点，因为

for (Set<Integer> subset : pSet) { 

} 

实际上等同于：

Iterator<PowerSet> it = pSet.iterator(); 
while (it.hasNext()) { 
    Set<Integer> subset = it.next(); 
} 

还要注意的是

if (bitSet.cardinality() == 0) { 
    return subset; 
} 

是多余的。尝试改为：

@Override 
public boolean hasNext() { 
    return i <= subsets; 
} 

@Override 
public Set<E> next() { 
    if (!hasNext()) { 
     throw new NoSuchElementException(); 
    } 
    Set<E> subset = new TreeSet<E>(); 
    BitSet bitSet = BitSet.valueOf(new long[] { i }); 
    for (int e = bitSet.nextSetBit(0); e != -1; e = bitSet.nextSetBit(e + 1)) { 
     subset.add(ary[e]); 
    } 
    i++; 

    return subset; 
}