时间戳

首页 > 解决方案 > 理解这个递归组合生成器

javascript - 理解这个递归组合生成器

问题描述

我发现这段代码用于为 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];
      }
    }
  };
}

标签： javascriptrecursionecmascript-6generatorcombinatorics

解决方案

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

所以让我们假设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)：

i我们从0to迭代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 = combination([], 1)，根据我们的假设不会产生任何结果，所以在这种情况下我们也不会产生任何结果。

因此，总的来说，我们产生了以下值：['a', 'b']、['a', 'c']、['a', 'd']、['b', 'c']、['b', 'd']和['c', 'd']，这正是来自 的两个元素的组合集合['a', 'b', 'c', 'd']。

您当然还需要检查基本情况，when 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}

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

推荐阅读