算法得到將N個項目拆分爲K個箱子的所有組合

Question

假設我有一個元素列表[1,2,3,4,]和一些箱子（讓我們假設2個箱子），我想列出所有組合的拆分項目1-4進入2箱。解決方案應該是這個樣子

[{{1}, {2,3,4}}, {{2}, {1,3,4}}, {{3}, {1,2,4}}, {{4}, {1,2,3}}, {{1,2}, {3,4}}, {{1,3}, {2,4}}, {{1,4}, {2,3}}, {{}, {1, 2, 3, 4}, {{1, 2, 3, 4}, {}}]

此外，爲了此事做 - 我沒有寫出來的所有的返回值，但{{1, 2, 3}, {4}}是{{3, 2, 1}, {4}}

Answer 1

不同的解決方案的常用方法如下： 。

如果您有，例如K分檔，請將K-1特殊值添加到您的初始數組中。我將使用-1值，假設它從不出現在初始數組中;你可以選擇一個不同的值。

因此，對於你的例子，最初的數組變成arr=[1,2,3,4,-1];如果K是例如4，則該陣列將是arr=[1,2,3,4,-1,-1,-1]。

現在列出陣列arr的所有排列組合。對於每個排列，將所有-1 s當作垃圾箱分隔符，因此所有元素都會首先進入第一個垃圾箱（按特定順序），第一個和第二個垃圾桶之間的所有元素都會轉到第二個垃圾箱，依此類推。

例如：

[-1,1,2,3,4] -> {{}, {1,2,3,4}} 
[2,1,3,-1,4] -> {{2,3,4}, {4}} 
[3,1,2,-1,4] -> {{3,1,2}, {4}} 
[1,3,-1,2,4] -> {{1,3}, {2,4}} 

等。

生成所有置換是一項標準任務（請參閱，例如，Permutations in JavaScript?），並且將數組拆分爲-1應該很容易。