combinations totaling to sum
combinations, matlab, permutation
Solution
For concreteness, let's go with your example of 3 values adding up to 6. The standard way to do this is to think of placing 2 'dividers' into a row of 6 identical 'objects': those dividers then divide the objects into 3 groups, and you can read off the length of each group. So all we need to do is enumerate all ways of placing those dividers. You can use `nchoosek(1:8, 2)` for this: each row of that matrix describes a division, by describing the positions of the 2 dividers amongst the `2 + 6 == 8` objects + dividers.
This is a more efficient approach than enumerating all triples of integers 0-6 and then picking out those that add to the correct total.
I don't really speak MATLAB, so the following is probably unidiomatic (and suggestions to improve it are welcome!), but something like this should work:
% Total we're aiming for.
n = 6;
% Number of pieces to divide that total into.
k = 3;
% All possible placements of internal dividers.
dividers = nchoosek(1:(n+k-1), k-1);
ndividers = size(dividers, 1);
% Add dividers at the beginning and end.
b = cat(2, zeros(ndividers, 1), dividers, (n+k)*ones(ndividers, 1));
% Find distances between dividers.
c = diff(b, 1, 2) - 1
And here are the results, as provided by this site:
c =
0 0 6
0 1 5
0 2 4
0 3 3
0 4 2
0 5 1
0 6 0
1 0 5
1 1 4
1 2 3
1 3 2
1 4 1
1 5 0
2 0 4
2 1 3
2 2 2
2 3 1
2 4 0
3 0 3
3 1 2
3 2 1
3 3 0
4 0 2
4 1 1
4 2 0
5 0 1
5 1 0
6 0 0
Problem
How would one go about generating a matrix with all the possible combinations of number totaling to a sum with repetition? Basically, combinations of `x1`, `x2`, `x3` such that `x1 + x2 + x3 = n`. For example: `n =3` ``` 0 1 2 0 2 1 1 0 2 1 2 0 1 1 1 ``` Is there simple way of doing this using predefined Matlab functions? I tried ``` n=6; nchoosek(0:n,3) ``` which gives me ``` 0 1 2 0 1 3 0 1 4 0 1 5 0 1 6 0 2 3 0 2 4 0 2 5 0 2 6 0 3 4 0 3 5 0 3 6 0 4 5 0 4 6 0 5 6 1 2 3 1 2 4 1 2 5 1 2 6 1 3 4 1 3 5 1 3 6 1 4 5 1 4 6 1 5 6 2 3 4 2 3 5 2 3 6 2 4 5 2 4 6 2 5 6 3 4 5 3 4 6 3 5 6 4 5 6 ``` How would one extract all rows that have the total equal to `n`? I think linear indexing or `find` should make it possible, but I don't know how to go about that. Regards