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

Question

我想找到所有可以将 n 项拆分到 m 个箱子中的方法。例如，对于 n=3 和 m=3，输出将是（顺序无关紧要）：

算法应该尽可能高效，最好是 vectorized/using 内置函数而不是 for 循环。谢谢！

Answer 1

这应该非常有效。

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

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

在 0、0 处拆分：这给出了长度的子区间 0、0、4。
在 0、1 处拆分：这给出了长度的子区间 0、1、3。
...
在 4、4 处拆分：这给出了长度的子区间 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

结果按字典顺序排列。

例如，对于 m = 3 箱中的 n = 4 项，输出为

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

Answer 2

我想提出一个基于外部函数和 accumarray 的解决方案（由于 repelem，它应该从 R2015a 开始工作）：

n = uint8(4); % number of items
m = uint8(3); % number of bins
whichBin = VChooseKR(1:m,n).'; % see FEX link below. Transpose saves us a `reshape()` later.
result = accumarray([repelem(1:size(whichBin,2),n).' whichBin(:)],1);

其中 VChooseKR(V,K) 创建一个矩阵，其行都是通过选择向量 V 的 K 个元素并重复创建的所有组合。

解释：

VChooseKR(1:m,n) 对于 m=3 和 n=4 的输出是：

 1     1     1     1
 1     1     1     2
 1     1     1     3
 1     1     2     2
 1     1     2     3
 1     1     3     3
 1     2     2     2
 1     2     2     3
 1     2     3     3
 1     3     3     3
 2     2     2     2
 2     2     2     3
 2     2     3     3
 2     3     3     3
 3     3     3     3

我们现在需要做的就是使用正整数 bin 对每一行的数字进行“histcount”以获得所需的结果。第一个输出行将是 [4 0 0] 因为所有 4 个元素都在 1^st bin 中。第二行将是 [3 1 0]，因为 3 个元素进入 1^st bin，1 个进入 2^nd，等等。

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

MATLAB generate all ways that n items can be put into m bins?

matlab

combinations

permutation

vectorization

解释：