生成幂集的所有元素

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)

所以，问题是：

我得到了所有元素（调试显示 next 仅针对 even i's 调用）。
不应该抛出异常。

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

生成幂集的所有元素

Generating all the elements of a power set

algorithm

data-structures

java-7