的JavaScript發生器功能超時試圖複製Python的itertools.combinations

Question

與一對夫婦的答案在這裏，我已經能夠開始學習發電機和開發以下功能的幫助時：

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。在 任何這些情況下，你應該返回一個空數組。

Answer 1

您可能可以在代碼複審中獲得更好的建議，但您可以嘗試的一項改進是修剪一些「死路徑」遞歸路徑。既然你知道每個結果的長度必須是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的副本。但是，與分支修剪相比，這更多是微型優化。首先嚐試修剪，看看每次改變會帶來多少改進。

最後，你也可以切換到迭代實現，看看是否有效。