理解这个递归组合生成器

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&nbsp;['c']、then&nbsp;'[d]'，同样combinations(['c', 'd'], 1)产生['c']then&nbsp;['d']，然后combinations(['d'], 1)产生 just&nbsp;['d']，最后combinations([], 1)什么也不产生。现在让我们来看看combinations(['a', 'b', 'c', 'd'], 2)：我们迭代ifrom0到3：当i=&nbsp;0,&nbsp;elements[i]='a'时，我们看到length是2，所以不是== 1。我们计算remaining &nbsp;= combinations(['b', 'c', 'd'], 1)，根据我们的假设，得出['b']then&nbsp;。因此，对于其中的每一个，我们都会屈服，这意味着我们屈服，然后['c']['d'][elements[i], ...(the yielded value)]['a', 'b']['a', 'c']['a', 'd']当i=&nbsp;1,&nbsp;elements[i]='b'时，我们看到 是length，2所以不是== 1。然后我们计算remaining = combinations(['c', 'd'], 1)，根据我们的假设，得出。因此，对于其中的每一个，我们都会产生，这意味着我们会产生，然后。['c']['d'][elements[i], ...(the yielded value)]['b', 'c']['b', 'd']当i=&nbsp;2,&nbsp;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) =>&nbsp;&nbsp; elements .flatMap ((el, i) =>&nbsp;&nbsp; &nbsp; length == 1&nbsp; &nbsp; &nbsp; ? [el]&nbsp; &nbsp; &nbsp; : combinations (elements .slice (i + 1), length - 1)&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; .map (combo => [el, ...combo])&nbsp; )&nbsp;&nbsp;console .log (combinations (['a', 'b', 'c', 'd'], 2)).as-console-wrapper {max-height: 100% !important; top: 0}