JavaScript 生成器函数在尝试复制 Python 的 itertools.combinations 时超时

Question

借助此处的几个答案，我已经能够开始学习生成器并开发以下功能：

function* icombinations(arr, k) {

  function* getCombinations(newArr, shift) {
    if (newArr.length === k) {
      yield newArr;
    }

    for (let i = shift; i < arr.length; i++) {
      yield* getCombinations([...newArr, arr[i]], i + 1);
    }
  }

  yield* getCombinations([], 0);

  return [];
}

这里是 link 到 repl.it: https://repl.it/E2QW/1

我可能还没有完全理解这个概念，因为上面的函数对于很长的输入会超时，因为我试图先生成所有可能的组合，然后产生每个组合。你知道我如何重构函数，这样我就不会先生成所有组合吗？

以下是我试图解决的挑战的描述：

Write a function called icombinations that should be a generator function with behavior similar to Python's itertools.combinations. You are given an array arr of unique items and an integer k.

You should yield each unique combination of elements in arr of length k with no replacements until there are no possible unique combinations left, at which point you should terminate the generator function. Your generator will be called with next(), and in some cases it will be called until completion.

Additionally It is important that you return combinations in the same order as the original array arr. (see the example below)....

For example:

given an array of unique elements example_arr and an integer example_k:

where example_arr = ['a', 'b', 'c', 'd'] and example_k = 2;

calling the next() method of the iterator should return [ 'a', 'b' ].

if we were to call next() again we should get [ 'a', 'c' ] and so on...

so that if we got all values yielded by the generator we would have the following:

[ 'a', 'b' ] [ 'a', 'c' ] [ 'a', 'd' ] [ 'b', 'c' ] [ 'b', 'd' ] [ 'c', 'd' ] again, notice the order of the above, as you will need to replicate it in your solution.

Some more things to consider:

If your solution is timing out, it may be because you tried to generate all possible combinations first and then yield each one. This defeats the point of a generator. Some of input values will be large.

Values in arr will always be unique but they may be of different types (i.e. strings, integers, other objects).

The only cases in which you would not be able to produce combinations is that in which arr is null or empty or has a length less than k. In any of those situations you should return an empty array.

Answer 1

您可能会在 Code Review 上获得更好的建议，但您可以尝试的一项改进是修剪一些 "dead-end" 递归路径。由于您知道每个结果的长度必须为 k，因此您应该仅在源数组中剩余的元素足以实际完成 k-子集时才递归。

function* icombinations(arr, k) {

    function* getCombinations(newArr, shift) {
        if (newArr.length === k) {
            yield newArr;
        } 
        // if what's available is >= what's needed
        else if (arr.length - shift >= k - newArr.length) {
            for (let i = shift; i < arr.length; i++) {
                yield* getCombinations([...newArr, arr[i]], i + 1);
            }
        }
    }

    yield* getCombinations([], 0);

    return [];
}

但是如果没有您的测试用例或对 arr.length 和 k 的限制，我们无法知道这是否足够好。您提到 arr.length 可能是 50，这意味着当 k 是 25 时最多有 126,410,606,437,752 个子集。无论算法多么高效，都无法在任何合理的时间内完成它。即使 k 为 5（或等价的 45），您也会看到 2,118,760 种组合。

您可以尝试的另一件事是在内部函数之外预先分配子集数组 (newArr)，然后在每次递归调用之前就地更新数组。这避免了每次要向其附加值时都需要复制 newArr，但您仍然需要在基本情况下生成 newArr 的副本。然而，与分支修剪相比，这更像是一种微观优化。先单独尝试修剪，看看每次更改能带来多少改进。

最后，您还可以切换到迭代实现，看看是否可行。

JavaScript 生成器函数在尝试复制 Python 的 itertools.combinations 时超时

JavaScript generator function times out when trying to replicate Python's itertools.combinations

javascript

python

combinations

permutation

ecmascript-6