的JavaScript发生器功能超时试图复制Python的itertools.combinations

-1

与一对夫妇的答案在这里，我已经能够开始学习发电机和开发以下功能的帮助时：的JavaScript发生器功能超时试图复制Python的itertools.combinations

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 []; 
}

这里一个链接到repl.it：https://repl.it/E2QW/1

我还没有完全理解这个概念，因为上面的函数超时输入非常长，因为我试图先生成所有可能的组合，然后产生每个组合。你知道我怎么可以重构该函数，以便我不首先生成所有组合？

这里是挑战，我试图解决的描述：

编写一个叫做icombinations功能，应该是类似于 Python的itertools.combinations行为发生器功能。您将获得独特项目的arr阵列和整数k。

你应该得到的元素的每个唯一组合在长度 k的arr没有更换，直到没有可能的唯一组合离开，此时，你应该终止发电机功能。你的发电机将被调用next()，在某些情况下，它将被调用直到完成。

此外，重要的是您以与原始数组arr相同的顺序返回组合。（参见下面的示例）....

例如：

给出独特元件的阵列example_arr和整数 example_k：

其中example_arr = ['a', 'b', 'c', 'd']和example_k = 2;

调用next()迭代器的方法应返回[ 'a', 'b' ]。

如果我们再次呼吁next()我们应该得到[ 'a', 'c' ]并因此 ...

因此，如果我们得到了由发电机产生的所有值，我们将有如下：

再次[ 'a', 'b' ] [ 'a', 'c' ] [ 'a', 'd' ] [ 'b', 'c' ] [ 'b', 'd' ] [ 'c', 'd' ] ，请注意上述顺序，因为您需要将复制到您的解决方案中。

做更多的事情要考虑：

如果解决方案已超时，这可能是因为你试图首先生成所有可能的组合，然后产生各一个。这破坏了发电机的重要性。一些输入值将是大。

arr中的值将始终是唯一的，但它们可能具有不同的类型（即字符串，整数，其他对象）。

您无法生成组合的唯一情况是arr为空或空或长度小于k。在任何这些情况下，你应该返回一个空数组。

来源

2016-11-18 Piotr Berebecki

不要先生成它们;这是有一个发电机的点。您的描述明确地说明了这一点（首先要考虑的事情）。 –

感谢Scott，我已经重复阅读了几次，并且我无法看到如何修改该功能。 –

我认为唯一的问题是'return []'。据我所知，那不属于那里。 –

您可能可以在代码复审中获得更好的建议，但您可以尝试的一项改进是修剪一些“死路径”递归路径。既然你知道每个结果的长度必须是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的副本。但是，与分支修剪相比，这更多是微型优化。首先尝试修剪，看看每次改变会带来多少改进。

最后，你也可以切换到迭代实现，看看是否有效。

来源

2016-11-18 18:28:28

的JavaScript发生器功能超时试图复制Python的itertools.combinations

回答

相关问题