使用 MATLAB 生成所有重复组合

问题描述

如何创建所有k-组合重复 使用 MATLAB 的给定集合(也称为 k-multicombinations 或 multisubsets)?

How do I create all k-combinations with repetitions of a given set (also called k-multicombinations or multisubsets) using MATLAB?

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

This is similar to the cartesian product, but two rows that only differ by their sorting should be considered the same (e.g. the vectors [1,1,2]=~=[1,2,1] are considered to be the same), so generating the cartesian product and then applying unique(sort(cartesianProduct,2),'rows') should yield the same results.

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

Example:The call nmultichoosek(1:n,k) should generate the following matrix:

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

推荐答案

我们可以使用维基百科文章中提到的双射，将不重复类型n+k-1选择k的组合映射到k-大小为n的多组合.我们生成不重复的组合并使用 bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1); 映射它们.这导致以下功能:

We can use the bijection mentioned in the wikipedia article, which maps combinations without repetition of type n+k-1 choose k to k-multicombinations of size n. We generate the combinations without repetition and map them using bsxfun(@minus, nchoosek(1:n+k-1,k), 0:k-1);. This results in the following function:

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

这篇关于使用 MATLAB 生成所有重复组合的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！