MATLAB Answers

Producing all combinations of a vector with replacement

19 views (last 30 days)
I am trying to produce all unique combinations of a vector with replacement, given some "choose" parameter, but neither the nchoosek() nor the perms() functions do exactly what I am trying to do.
For example, all unique combinations of the integers 1 and 2, derived manually, are:
uc = [1 1; 1 2; 2 2]
uc =
1 1
1 2
2 2
Similarly, all unique combinations of the integers 1, 2, and 3, choosing only two in any permutation are:
uc2 = [1 1; 1 2; 1 3; 2 2; 2 3; 3 3]
uc2 =
1 1
1 2
1 3
2 2
2 3
3 3
The C output for nchoosek() does not produce the desired result because it returns all possible combinations without replacement. For example:
L2 = [1 2];
L2k2 = nchoosek(L2,2)
L2k2 =
1 2
L3 = [1 2 3];
L3k2 = nchoosek(L3,2)
L3k2 =
1 2
1 3
2 3
The perms() function also does not work for this purpose because it both samples without replacement and produces duplicate combinations. For example:
test1 = perms(L2)
test2 = perms(L3)
test1 =
2 1
1 2
test2 =
3 2 1
3 1 2
2 3 1
2 1 3
1 3 2
1 2 3
Is there a way to toggle the settings of the nchoosek() function so that it produces all possible combinations of a vector v, given k values in each row, with replacement?
Thank you in advance.
  1 Comment
May_the_degrees_of_freedom_be_with_you
Thank you to David and Jonas for providing those answers! I really do appreciate the help. I tried both and they worked!

Sign in to comment.

Accepted Answer

David Hill
David Hill on 13 Jul 2021
[x,y]=meshgrid(1:4);
z=unique(sort([x(:),y(:)],2),'rows');

More Answers (2)

Jonas
Jonas on 13 Jul 2021
you could e.g. use
nchoosek(repelem(1:3,2),2)
but then you whould have to use unique(...,'rows') on the resulting combinations

May_the_degrees_of_freedom_be_with_you
Update for anyone else interested in this topic:
The user created function, combinator(), appears to provide all the benefits of the nchoosek() function, along with the ability to toggle between permutations and combinations, each with and without replacement/repitition. Documentation: https://www.mathworks.com/matlabcentral/fileexchange/24325-combinator-combinations-and-permutations
Before trying to write code, I mapped combinations out manually for n = 2:4 and k = 2:5. combinator() produces exactly what I drew out manually for those varying combinations of n and k. Very grateful to Matt Fig for writing this algorithm.
That said, I'm still curious to hear more from the Matlab community on the nchoosek() function. I actually came across Pascal's triangle because I noticed patterns in the combinations I was writing out, and it turns out the number of unique combinations, with replacement, follows Pascal's triangle exactly. Specifically, the number of unique combinations with replacement corresponds to the diagonals in Pascal's triangle, starting with the series of traingular numbers (3, 6, 10, 15, 21), then tetrahedral numbers (4. 10, 20, 35), and so on. So, I'm curious as to why the C output for the nchoosek() function does not have this capability. Maybe I'm missing an area in the documentation, but it seems like something Matlab would have developed in house.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!