4

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

Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
Ash
  • 318
  • 3
  • 14
  • You'd use logical indexing: `result = c(sum(c,2)==n,:);`, where `c` is the result of `nchoosek`. But `nchoosek` won't do, as it does not give repetitions – Luis Mendo Feb 01 '14 at 16:33
  • 1
    The standard way to do this is to imagine placing two dividers into a row of 6 objects, to obtain 3 separate partitions. So you're looking at permuting 8 things: combinations of the 6 objects and the 2 dividers. You should be able to manipulate the results of e.g., `nchoosek(1:8, 2)` to give you what you need. That's *much* more efficient than generating all combinations and choosing those with the correct sum. – Mark Dickinson Feb 01 '14 at 16:54
  • E.g., here's the corresponding thing in Python: `[(a, b-a-1, 7-b) for a, b in itertools.combinations(range(8), 2)]`. (I don't have Matlab available here to experiment with, but you or someone else may be able to translate this.) – Mark Dickinson Feb 01 '14 at 16:59

5 Answers5

7

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
Mark Dickinson
  • 29,088
  • 9
  • 83
  • 120
1

Use dec2base to generate all combinations with repetition, and logical indexing to keep only those with the desired sum:

n = 6;
m = 3;
c = dec2base(0:(n+1)^m-1,n+1,m)-'0'; %// generate combinations with repetition
result = c(sum(c,2)==n,:); %// keep those with desired sum. Logical indexing
Luis Mendo
  • 110,752
  • 13
  • 76
  • 147
0

I believe you are describing permutations of restricted integer partitions, though your example doesn't seem complete. For n=3 into three parts from elements {0, 1, 2} there are two solutions: {0, 1, 2} and {1, 1, 1}. These may further be permuted into:

{{0, 1, 2}, {0, 2, 1}, {1, 0, 2}, {1, 2, 0}, {2, 0, 1}, {2, 1, 0}, {1, 1, 1}}

If this is not what you want you should clarify why these additional orderings are not to be included.

If this understanding is correct you should be able to find a number of resources by searching for that phrase. Some examples:

Elegant Python code for Integer Partitioning

Integer Partition in Java

Algorithm for generating integer partitions

Integer Partition Algorithm by Jerome Kelleher

Integer Partition Algorithm by Daniel Scocco

Fast Algorithms for Generating Integer Partitions (PDF) (looks heavy-duty)

Stony Brook Algorithm Repository - Partitions

As a practical example, using Mathematica one would write:

IntegerPartitions[6, {3}, Range[0, 5]]

Output:

{{5, 1, 0}, {4, 2, 0}, {4, 1, 1}, {3, 3, 0}, {3, 2, 1}, {2, 2, 2}}

These could each then be permuted to produce the other orderings.

It is quite easy to set up a recursive function to generate these partitions by starting with all numbers <= n, then appending values that are <= that value that do not exceed n. This is continued until each list is length p; if the list totals n it is kept; if it does not it is discarded. Again, in Mathematica:

f[n_, p_, c__] /; Length@{c} == p := If[+c == n, {{c}}, {}]
f[n_, p_, c___] := Array[f[n, p, c, #] &, Min[c, n - +c] + 1, 0, Join]

f[6, 3]

Output:

{{2, 2, 2}, {3, 2, 1}, {3, 3, 0}, {4, 1, 1}, {4, 2, 0}, {5, 1, 0}, {6, 0, 0}}
Community
  • 1
  • 1
Mr.Wizard
  • 24,179
  • 5
  • 44
  • 125
0

The function nchoosek provides the possible ways of selecting r-1 plus signs in the sum. For example, x1 + x2 + x3 = 5, then two signals must be selected over the sum 1 + 1 + 1 + 1 + 1 = 5. For nonnegative solutions make the transformation yi = x1 + 1, and solves y1+y2+ ... = m + n

The result of nchoosek provides the position of the plus sign.

The remaining of program provides the sum between selected signals.

clear all    
close all    
clc    

% Program that generates the possible distributions
% M objects in r boxes 
% Éderson D'Martin Costa    
% 12/02/2015    

% number of objects
m = 3;    

% number of boxes    
r = 3;

% total number of possibilities
% C = nchoosek(m+r-1,r-1)

v = 1:m+r-1;    
C = nchoosek(v,r-1);    
[l,c] = size(C);    
Y = zeros(l,c+1);    
Y(:,1) = C(:,1);    
Y(:,end) = m+r-C(:,end);

for i = r-1:-1:2    
    Y(:,i) = C(:,i)-C(:,i-1);    
end    

X = Y-1;    
display(X)    
% sum(X,2)
0

As @Mark Dickinson pointed out. I just wanted to give intuitive explanation.

Your problem can be restated as "How many ways can you distribute 3 apples to 3 people"?

Suppose you have 3 people: AA, BB, CC and you want to distribute 3 apple among them. How can you do it?

AA   |    BB     | CC
***  |           | 
*    |     *     | *
**   |     *     | 
........
* -> represent apples.

Now if you think the problem is just selecting two | among 5 positions which we know can be done using 5 choose 2.

noman pouigt
  • 906
  • 11
  • 25