如何将排列函数转换为惰性生成器？

Question

我正在尝试使用生成器逐个获取数组的所有排列。

这是原始代码（按预期工作并返回排列数组），下面是我尝试更改它的代码：

function permutations(iList, maxLength) {
        const cur = Array(maxLength)
        const results = []

        function rec(list, depth = 0) {
            if (depth === maxLength) {
                return results.push(cur.slice(0))
            }
            for (let i = 0; i < list.length; ++i) {
                cur[depth] = list.splice(i, 1)[0]
                rec(list, depth + 1)
                list.splice(i, 0, cur[depth])
            }
        }
        rec(iList)
        return results
    }

我的代码，没有返回任何内容：

function* permutations2(iList, maxLength) {
    const cur = Array(maxLength)

    function* rec(list, depth = 0) {
        if (depth === maxLength) {
            yield cur.slice(0)
        }
        for (let i = 0; i < list.length; ++i) {
            cur[depth] = list.splice(i, 1)[0]
            rec(list, depth + 1)
            list.splice(i, 0, cur[depth])
        }
    }
    yield rec(iList)
 }

例如，对于print(permutations2([1, 2, 3], 2))，我想要得到

[1, 2]
[1, 3]
[2, 1]
[2, 3]
[3, 1]
[3, 2]

然而，使用原始代码我得到了一个排列的数组：

[[1, 2],
[1, 3],
[2, 1],
[2, 3],
[3, 1],
[3, 2]]

我很希望能够理解为什么我的代码不能运行，以及如何修复它。 谢谢！

- Matan

---

你是否正在尝试创建一个“惰性”生成器，它只在需要计算值时才进行计算？ - zenly

@kelly 是的 - 我不需要一次性获得所有排列 - 每次只需要一个。使用完毕后，我就不再需要它，可以继续使用下一个排列。 - Matan

这个问题的详细信息中应包括一个带有预期输出的示例输入数组。 - jsejcksn

@jsejcksn 你说得完全正确 - 我添加了一个例子。 - Matan

Answer 1

懒惰的生成器需要更多的工作。

不要立即返回结果，而是使用yield*来产生从rec中出现的所有结果。

现在rec也是一个生成器函数。

类似地，我们不再使用return并添加到结果数组中，而是使用yield来产生结果。

这里需要更改的是添加else，因为yield不会停止函数的其余部分执行。它只是暂停。这就是为什么我们需要else来确保在我们产生后不执行此代码。

在else内部，与上述相同，每当我们调用rec时，我们还需要产生rec的结果。

function* permutations(iList, maxLength) {
    const cur = Array(maxLength)

    function* rec(list, depth = 0) {
        if (depth === maxLength) {
            yield cur.slice(0);
        } else {
            for (let i = 0; i < list.length; ++i) {
                cur[depth] = list.splice(i, 1)[0];

                yield* rec(list, depth + 1);

                list.splice(i, 0, cur[depth])
            }
        }
    }

    yield* rec(iList);
}

console.log([...permutations([1, 2, 3], 2)]);

这似乎产生了相同的结果，但现在它是懒惰的。

- zenly

---

谢谢 - 看起来这似乎有效。 我修改了我的代码，像这样： 将 for (const perm of permutations([1, 2, 3], 2)) 改为 const generator = permutations([1, 2, 3], 2) let perm = generator.next() while (perm.done === false){ .... ; perm = generator.next(); - Matan

Answer 2

这实际上是你需要的所有更改，生成器函数，然后使用yield*而不是return。

function* permutations(iList, maxLength) {
    const cur = Array(maxLength)
    const results = []

    function rec(list, depth = 0) {
        if (depth === maxLength) {
            return results.push(cur.slice(0))
        }
        for (let i = 0; i < list.length; ++i) {
            cur[depth] = list.splice(i, 1)[0]
            rec(list, depth + 1)
            list.splice(i, 0, cur[depth])
        }
    }
    rec(iList);
    yield* results;
}

console.log([...permutations([1, 2, 3], 2)]);

请注意，这将创建一个非惰性生成器。它会预先计算所有值，然后依次产出它们。

yield* 是一种快速产出可迭代对象或另一个生成器的所有元素的方法。

- zenly

---

我该如何将其修改为惰性生成器？ - Matan

这会提前生成所有排列，然后一次只产生一个。我对 OP 的问题的理解（也是迭代概念的优点之一）是他们想要延迟工作，只在每个迭代周期中完成。 - jsejcksn

@jsejcksn 是的 - 就像你说的那样。我该如何实现？ - Matan