理解这个递归组合生成器

Question

我发现这段代码用于生成 n 选择 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']、then ['c']、then '[d]'，同样combinations(['c', 'd'], 1)产生['c']then ['d']，然后combinations(['d'], 1)产生 just ['d']，最后combinations([], 1)什么也不产生。

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

我们迭代ifrom0到3：

• 当i= 0, elements[i]='a'时，我们看到length是2，所以不是== 1。我们计算remaining  = combinations(['b', 'c', 'd'], 1)，根据我们的假设，得出['b']then 。因此，对于其中的每一个，我们都会屈服，这意味着我们屈服，然后['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。我们计算“剩余=组合（[]，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}