Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Generating all combinations with repetition using MATLAB

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

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.

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
like image 350
knedlsepp Avatar asked Feb 02 '15 18:02

knedlsepp


People also ask

How do you generate all possible combinations of a set of numbers in Matlab?

C = combntns( v , k ) returns all possible combinations of the set of values v , given combinations of length k .

How do you find all possible repetition combinations?

The number of k-element combinations of n objects, with repetition is Cn,k = Cn+k-1,k = (n + k − 1 k ) = ((n k )) . It is also the number of all ways to put k identical balls into n distinct boxes, or the number of all functions from a set of k identical elements to a set of n distinct elements.

How do you make a combination in Matlab?

b = nchoosek( n , k ) returns the binomial coefficient of n and k , defined as n!/(k!( n - k)!) . This is the number of combinations of n items taken k at a time. C = nchoosek( v , k ) returns a matrix containing all possible combinations of the elements of vector v taken k at a time.


2 Answers

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
like image 113
knedlsepp Avatar answered Nov 16 '22 02:11

knedlsepp


Thanks to Hans Hirse for a correction.

Brute-force approach: generate all tuples and then keep only those that are sorted. 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, 1),:);  %'// keep only those that are sorted
like image 25
Luis Mendo Avatar answered Nov 16 '22 02:11

Luis Mendo