使用 MATLAB 生成所有重复组合

Question

如何使用 MATLAB 创建给定集合的所有 k-combinations with repetitions（也称为 k-multicombinations 或 multisubsets）？

这类似于笛卡尔积，但仅排序不同的两行应被视为相同（例如，向量 [1,1,2]=~=[1,2,1] 被视为相同），因此生成笛卡尔积和然后应用 unique(sort(cartesianProduct,2),'rows') 应该会产生相同的结果。

示例： 调用 nmultichoosek(1:n,k) 应生成以下矩阵：

nmultichoosek(1:3,3)
ans =
     1     1     1
     1     1     2
     1     1     3
     1     2     2
     1     2     3
     1     3     3
     2     2     2
     2     2     3
     2     3     3
     3     3     3

Answer 1

我们可以使用 wikipedia article 中提到的双射，它将不重复类型 n+k-1 choose k 的组合映射到 k-大小 n 的多重组合。我们生成没有重复的组合，并使用 bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1); 映射它们。这导致以下功能：

function combs = nmultichoosek(values, k)
%// Return number of multisubsets or actual multisubsets.
if numel(values)==1 
    n = values;
    combs = nchoosek(n+k-1,k);
else
    n = numel(values);
    combs = bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);
    combs = reshape(values(combs),[],k);
end

Answer 2

感谢Hans Hirse更正。

蛮力法：生成所有元组，然后仅保留排序好的元组。不适合 n 或 k.

的大值

values = 1:3;                               %//  data
k = 3;                                      %//  data
n = numel(values);                          %//  number of values
combs = values(dec2base(0:n^k-1,n)-'0'+1);  %//  generate all tuples
combs = combs(all(diff(combs.')>=0, 1),:);  %'// keep only those that are sorted

Answer 3

这可能是一种比以前的帖子更残酷（内存密集型）的方法，但却是一个整洁可读的单行代码：

 combs = unique(sort(nchoosek(repmat(values,1,k),k),2),'rows');

使用 MATLAB 生成所有重复组合

Generating all combinations with repetition using MATLAB

matlab

combinations

combinatorics

multiset