Create all repeating combinations using MATLAB

Question

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

This is similar to the Cartesian product, but two lines that differ only in their sorting should be treated the same way (for example, the vectors [1,1,2]=~=[1,2,1] are considered the same), therefore, generating the Cartesian product, and then applying unique(sort(cartesianProduct,2),'rows') should give the same results.

Example: A call to 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 

Answer 1

We can use the bijection mentioned in the wikipedia article, which displays combinations without repeating the type n+k-1 choose k to k -multiple combinations of size n . We generate combinations without repetition and match 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 

Answer 2

This is probably an even more brutal (intense) method than previous posts, but a convenient readable single-line:

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

Answer 3

Brute force method: generate all tuples, and then only save sorted ones. Not suitable for large values ​​of n or 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),:); %'// keep only those that are sorted