java - 如何使这个算法变得懒惰？（爪哇）

Question

让我们考虑一个函数P(n)，它将自然数作为输入并返回这样的输出：

P(1) = [[0], [1]]
P(2) = [[0, 0], [1, 0], [0, 1], [1, 1]]
P(3) = [[0, 0, 0], [1, 0, 0], [0, 1, 0], [1, 1, 0], [0, 0, 1], [1, 0, 1], [0, 1, 1], [1, 1, 1]]
P(4) = [[0, 0, 0, 0], [1, 0, 0, 0], [0, 1, 0, 0], [1, 1, 0, 0], [0, 0, 1, 0], [1, 0, 1, 0], [0, 1, 1, 0], [1, 1, 1, 0], [0, 0, 0, 1], [1, 0, 0, 1], [0, 1, 0, 1], [1, 1, 0, 1], [0, 0, 1, 1], [1, 0, 1, 1], [0, 1, 1, 1], [1, 1, 1, 1]]

我不知道这是如何正式调用的（组合？），但我认为这个例子足以理解我的想法。

我使用 Java 来实现：

static byte[][] permutate(int n) {
    byte[][] ps = new byte[1 << n][n];
    go(ps, 0, ps.length / 2, ps.length, n - 1);
    return ps;
}

static void go(byte[][] as, int l, int m, int h, int depth) {
    if (depth < 0)
        return;

    for (int i = l, j = m; i < m && j < h; ++i, ++j) {
        as[i][depth] = 0;
        as[j][depth] = 1;
    }

    go(as, l, (l + m) / 2, m, depth - 1);
    go(as, m, (m + h) / 2, h, depth - 1);
}

此实现返回正确的结果，但它的内存使用量呈指数增长，特别是在O(2^n)！

---

这就是我想要的：这个功能，但懒惰！仅在需要时生成这些元组（它们实际上是数组，但这无关紧要）并丢弃已使用的元组。所以，我的问题：

这个函数是否有可能返回一个迭代器而不是一个数组？如果是这样，怎么做？

标签： javaarraysiteratorlazy-evaluation

Answer 1

您可以使用不使用递归的不同方法：

public static void main(String[] args) throws Exception {
    Iterator<byte[]> iterator = new PermutationIterator(4);
    while (iterator.hasNext()) {
        System.out.println(Arrays.toString(iterator.next()));
    }
}

private static final class PermutationIterator implements Iterator<byte[]> {
    private final int max;
    private final int n;
    private int current;

    public PermutationIterator(int n) {
        this.n = n;
        this.max = (int) Math.pow(2, n);
    }

    @Override
    public boolean hasNext() {
        return current < max;
    }

    @Override
    public byte[] next() {
        byte[] bytes = new byte[n];
        for (int i = 0; i < n; i++) {
            bytes[i] = (byte) ((current >>> i) & 1);
        }
        current++;
        return bytes;
    }

但是，请注意，这只会产生正确的结果n <= 31。如果你想支持更大的n，你应该使用long甚至BigInteger.

输出：

[0, 0, 0, 0]
[1, 0, 0, 0]
[0, 1, 0, 0]
[1, 1, 0, 0]
[0, 0, 1, 0]
[1, 0, 1, 0]
[0, 1, 1, 0]
[1, 1, 1, 0]
[0, 0, 0, 1]
[1, 0, 0, 1]
[0, 1, 0, 1]
[1, 1, 0, 1]
[0, 0, 1, 1]
[1, 0, 1, 1]
[0, 1, 1, 1]
[1, 1, 1, 1]