迭代器迭代给定大小的所有子集[重复]

Question

在我的应用程序中，我需要数组1的给定大小k的所有子集。。n

这可以使用递归方法轻松完成，并存储沿途找到的所有子集。然而，我不希望我的应用程序使用指数级的内存量[O（n^k）]。

因此，我想编写一个实现（Java）Iterator的类来迭代所述子集。

public class SubsetIterator implements Iterator<int[]> {

    private int k;
    private int[] array;

    public SubsetIterator(int k, int[] array) {
        this.k     = k;
        this.array = array;
    }

    @Override
    public boolean hasNext() {
        //To be implemented.
    }

    @Override
    public int[] next() {
        //To be implemented.
    }
}

所以我可以如下使用它：

SubsetIterator iter = new SubsetIterator(k, array);

while (iter.hasNext) {
    int[] next = iter.next();
    //Do stuff
}

显然，我们需要存储Next（）最后返回的当前子集，它被初始化为1... k。但是如何从这个当前子集计算下一个子集呢？

Answer 1

我认为您应该使用存储所有子集的方法，如果这对您的用例是可能的。否则，每次使用迭代器时，您将分配相同数量的内存，这将使GC非常努力地工作。