(MATLAB) ALL integer positive solutions for a linear equation

Question

I want to generate a list, named listt, that contains all possible positive integers that sum into a specific number d. For example, I am looking at the list of all the possible positive integer values for x's such that x1 + x2 + ... + xk = d.

In this case, the row size of listt should be (d+k-1) choose (k-1).

I already have the MATLAB code for doing that (see below), but the main problem is that this code allows repetitive rows in listt. I need help in order to change this code suth that there are no repetitive rows in listt.

k = 2;
d = 2;
m = nchoosek(d+k-1, k-1);

% generate non-negative integer random (m x k) array row-sum to d 
ss=rand(m,d+k-1);
[~,r] = maxk(ss,k-1,2);
z = zeros(m,1);
listt = diff([z, sort(r,2), (d+k)+z],1,2)-1;

Let's say d=5 and k=2. Assume I get the following listt:

 1     4
 2     3
 0     5
 5     0
 5     0
 0     5

So as you can see, the row (5,0) and row (0,5) are repeated two times each. I want to get unique rows.

More precisely, for d=5 and k=2, what do I want to get exactly is the following all 6 possibilities:

 1     4
 2     3
 0     5
 5     0
 4     1
 3     2

Any help will be very appreciated!

Answer 1

Let d denote the desired sum and k the number of components.

d = 5; % desired sum
k = 2; % desired number of components
b = nchoosek(1:d+k-1, k-1);
t = [ones(size(b,1),1) b+1 repmat(d+k+1, size(b,1),1)];
result = diff(t, [], 2)-1;

The code works by representing each solution as a row vector containing k+1 increasing integers starting at 1 and ending at d+k+1 (matrix t in the code). The k-1 inner integers are generated using nchoosek. The actual solution is then obtained from the k consecutive differences between those integers.

For example, the matrix t for inputs d=5 and k=2 is

1     2     8
1     3     8
1     4     8
1     5     8
1     6     8
1     7     8

which gives the result

0     5
1     4
2     3
3     2
4     1
5     0

Answer 2

This is called partition of an integer. It is exponential in n, and there is a good implementation in Python, https://ics.uci.edu/~eppstein/PADS/IntegerPartitions.py.

I found MATLAB implementation, but never used it: https://www.mathworks.com/matlabcentral/fileexchange/36437-integer-partition-generator

In this case, the row size of listt should be (d+k-1) choose (k-1)

not sure how you got this result, partition function p(n) is about

p(n) ~ 1/(4 n sqrt(3)) exp(pi sqrt(2 n / 3))

UPDATE

If you need only partitions which have specific length, then you could run partition algorithm for a given d till first output exceeding k numbers. Didn't try MATLAB algorithm, but Python and other I tried were all going from shortest partition to longest one. Easy to check for specific length and break.

UPDATE II

Downloaded MATLAB package and ran it using Octave. It has interface you're asking for, e.g.

d = 6;
k = 3;

s=intpartgen(d,k);

produced

6  0  0
5  1  0
4  1  1
3  2  1
4  2  0
2  2  2
3  3  0

Answer 3

Ok, I got it - you really wanted not partition, but composition !

Ok, there is good MATLAB package exactly for that: https://www.mathworks.com/matlabcentral/fileexchange/27110-restricted-integer-composition

Example using it:

d=6;
k=3;

jdoric( d,k,k,0,d );

will print

   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
   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
   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
   4   0   2
   4   1   1
   4   2   0
   5   0   1
   5   1   0