combinations totaling to sum

Question

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

Answer 1

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