Generating all combinations with repetition using MATLAB

Question

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

score 20 · Accepted Answer · answered Feb 02 '15 at 18:51

20

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

answered Feb 02 '15 at 18:51

knedlsepp

6,065
3
20
41

Ver fast and memory-efficient! Great question and answer – Luis Mendo Feb 02 '15 at 20:16
Do you really need that `reshape`? Isn't `combs = values(combs);` enough? – Luis Mendo Feb 02 '15 at 20:39
2

@LuisMendo: I just did it, so for `k=1` it will return a column vector. Otherwise it could be omitted. – knedlsepp Feb 02 '15 at 22:31

Luis Mendo · Answer 2 · 2019-11-12T09:44:41.717

2

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

edited Nov 12 '19 at 09:44

answered Feb 02 '15 at 20:05

Luis Mendo

110,752
13
76
147

May I suggest the following change: `combs = combs(all(diff(combs.')>=0, 1),:);` For `k = 2`, the result of the `diff` is a `1 x m` vector, such that `all` works along the second axis, but what you want is `all` (explicitly) working along the first axis, so setting the `dim` parameter to `1` now enables this solution to also work for `k = 2`. :-) – HansHirse Nov 12 '19 at 06:07
@HansHirse You are totally right. Updated, thank you! – Luis Mendo Nov 12 '19 at 09:45

score 1 · Answer 3 · answered Mar 07 '15 at 21:33

1

This is probably an even more brutal (memory intensive) method than previous posts, but a tidy readable one-liner:

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

answered Mar 07 '15 at 21:33

Buck Thorn

5,024
2
17
27

Generating all combinations with repetition using MATLAB

3 Answers3

Linked