MATLAB生成n个项目可以放入m个箱子的所有方法吗？

Question

我想找到n可以在m箱子之间拆分物品的所有方法.例如,for n=3和m=3输出将是(顺序无关紧要):

[3 0 0
 0 3 0
 0 0 3
 2 1 0
 1 2 0
 0 1 2
 0 2 1
 1 0 2
 2 0 1
 1 1 1]

算法应该尽可能高效,最好是矢量化/使用内置函数而不是for循环.谢谢!

Answer 1

这应该非常有效.

它的工作原理是在m -1整数值,可能是重合的分裂点处生成实际区间[0,n ]的所有可能的分割.生成的子区间的长度给出了解决方案.

例如,对于n=4和m=3,在m -1点分割区间[0,4]的一些可能方法是:

• 在拆分0,0:这给lenghts的子区间0,0,4.
• 在拆分0,1:这给lenghts的子区间0,1,3.
• ...
• 在拆分4,4:这给lenghts的子区间4,0,0.

码:

n = 4; % number of items
m = 3; % number of bins
x = bsxfun(@minus, nchoosek(0:n+m-2,m-1), 0:m-2); % split points
x = [zeros(size(x,1),1) x n*ones(size(x,1),1)]; % add start and end of interval [0, n]
result = diff(x.').'; % compute subinterval lengths

结果按字典顺序排列.

例如,对于箱中的n = 4项目,m = 3输出是

result =
     0     0     4
     0     1     3
     0     2     2
     0     3     1
     0     4     0
     1     0     3
     1     1     2
     1     2     1
     1     3     0
     2     0     2
     2     1     1
     2     2     0
     3     0     1
     3     1     0
     4     0     0