算法得到将N个项目拆分为K个箱子的所有组合

假设我有一个元素列表[1,2,3,4,]和一些箱子（让我们假设2个箱子），我想列出所有组合的拆分项目1-4进入2箱。解决方案应该是这个样子算法得到将N个项目拆分为K个箱子的所有组合

[{{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}}

来源

2015-06-16 Atul Bhatia

[算法从n返回k元素的所有组合]的可能重复（http://stackoverflow.com/questions/127704/algorithm-to-return-all-combinations-of-k-elements-from-n ） –

您是否缺少{{}，{1,2,3,4}}？ –

是的，应该包含在解决方案中，对不起 –

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

如果您有，例如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应该很容易。

来源

2015-06-16 18:51:18 Petr

非常有趣 - 将看看这个解决方案 –

算法得到将N个项目拆分为K个箱子的所有组合

回答

相关问题