如何让这个算法懒惰？ (Java)

Question

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

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

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

这就是我想要的：这个功能，但是很懒！只在需要时生成这些元组（它们实际上是数组，但这不是重点）并丢弃已经使用的元组。所以，我的问题：

这个函数可以return一个迭代器而不是一个数组吗？如果是，怎么做？

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]

如何让这个算法懒惰？ (Java)

How to make this algorithm lazy? (Java)

java

arrays

iterator

lazy-evaluation