理解这个递归组合生成器

Question

我找到了这段用于为 n choose k 组合生成生成器函数的代码，但我不太明白。有人可以帮我用通俗易懂的英语解释背后的步骤吗？谢谢

const combinations = function*(elements, length) {
  for (let i = 0; i < elements.length; i++) {
    if (length === 1) {
      yield [elements[i]];
    } else {
      let remaining = combinations(elements.slice(i + 1, elements.length), length - 1);
      for (let next of remaining) {
        yield [elements[i], ...next];
      }
    }
  };
}

Answer 1

理解这种递归情况的典型方法是假设它适用于较小的情况，然后再看看较大的情况如何进行。

所以我们假设 combinations(['b', 'c', 'd'], 1) 产生值 ['b']，然后是 ['c']，然后是 '[d]'，类似地 combinations(['c', 'd'], 1) 产生 ['c'] 然后是 ['d']，然后 combinations(['d'], 1) 只产生 ['d']，最后 combinations([], 1) 什么也没有产生。

现在让我们来看看 combinations(['a', 'b', 'c', 'd'], 2):

我们从 0 迭代 i 到 3:

当i = 0, elements[i] = 'a' 我们看到 length 是 2,所以不是 == 1。然后我们计算 remaining = combinations(['b', 'c', 'd'], 1)，根据我们的假设，它会产生 ['b'] 然后 ['c'] 然后 ['d']。因此，对于其中的每一个，我们都会产生 [elements[i], ...(the yielded value)]，这意味着我们会产生 ['a', 'b']，然后是 ['a', 'c']，然后是 ['a', 'd']
当 i = 1, elements[i] = 'b' 并且我们看到 length 是 2,所以不是 == 1。然后我们计算 remaining = combinations(['c', 'd'], 1)，根据我们的假设，它会产生 ['c'] 然后 ['d']。所以对于其中的每一个，我们产生 [elements[i], ...(the yielded value)]，这意味着我们产生 ['b', 'c']，然后是 ['b', 'd'].
当 i = 2, elements[i] = 'c' 并且我们看到 length 是 2,所以不是 == 1。然后我们计算 remaining = combinations(['d'], 1)，根据我们的假设得出 ['d']。因此，对于其中的（唯一）一个，我们产生 [elements[i], ...(the yielded value)]，这意味着我们产生 ['c', 'd'].
并且当 i = 3、elements[i] = 'd' 并且我们看到 length 是 2 ，所以不是 == 1。然后我们计算 `remaining = combinations([], 1)，根据我们的假设，它不会产生任何结果，因此在这种情况下我们也不会产生任何结果。

因此，总体而言，我们得出了以下值：['a', 'b']、['a', 'c']、['a', 'd']、['b', 'c']、['b', 'd'] 和 ['c', 'd'], 这正是 ['a', 'b', 'c', 'd'].

中两个元素的组合集合

当 length = 1 时，您当然也需要检查基本情况，但这应该很容易做到。

非生成器方法

有时，生成器方法会使代码更清晰、更易于理解。不过，这并不是真正的时代之一。

基本上，生成器让您不必进行复杂的结果收集，而是 yield 随手收集。如果您可以同样轻松地收集结果，那么非生成器代码通常会更简单。这是不使用生成器的相同算法：

const combinations = (elements, length) => 
  elements .flatMap ((el, i) => 
    length == 1
      ? [el]
      : combinations (elements .slice (i + 1), length - 1) 
          .map (combo => [el, ...combo])
  )
  
console .log (combinations (['a', 'b', 'c', 'd'], 2))

.as-console-wrapper {max-height: 100% !important; top: 0}

我当然觉得这更容易理解。

理解这个递归组合生成器

Understanding this recursive combination generator

javascript

recursion

ecmascript-6

generator

combinatorics

非生成器方法