Thread Subject: integer solutions for x_1+x_2+...+x_n = k

Help.. please..

I need to write a function for solving

x_1+x_2+x_3+ ...+x_n = k

where n and k are inputs, k is some small positive integer, for example, k= 3, or k= 6, n is rather large positve integer, for example,, n = 20, or n= 60.


The unknowns x_1, x_2, ...x_n are non-negative integers.


I wrote a complicated loop to list out lexicographically all (x_1, x_2, ..., x_n) such that x_1+x_2+x_3+ ...+x_n <= k, then select out the ones that satisfy the desired equality.


It works well when n is small, like n= 20, but when n is bigger, it does not work out at all, Matlab is busy for many many hours without giving any result...

Are there any smarter ways to do it?

Thank you!!

Oriole wrote:
 
> I need to write a function for solving

> x_1+x_2+x_3+ ...+x_n = k

> where n and k are inputs, k is some small positive integer, for example, k= 3, or k= 6,
> n is rather large positve integer, for example,, n = 20, or n= 60.

> The unknowns x_1, x_2, ...x_n are non-negative integers.

Ian posted complete code in
http://groups.google.ca/group/comp.soft-sys.matlab/msg/aa62015340cfea84


--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

"Oriole " <oriole_ni@hotmail.com> wrote in message <geku21$eku$1@fred.mathworks.com>...

>
> It works well when n is small, like n= 20, but when n is bigger, it does not work out at all, Matlab is busy for many many hours without giving any result...
>

Have you check the number of solutions for large n? It might be not possible to compute.

Here is code in FEX that can accomplish that, but again, try to look at the feasibility before solving: http://www.mathworks.com/matlabcentral/fileexchange/17818

Bruno

Walter Roberson wrote:
> Oriole wrote:

>> I need to write a function for solving

>> x_1+x_2+x_3+ ...+x_n = k

>> where n and k are inputs, k is some small positive integer, for
>> example, k= 3, or k= 6,
>> n is rather large positve integer, for example,, n = 20, or n= 60.

>> The unknowns x_1, x_2, ...x_n are non-negative integers.

> Ian posted complete code in

By the way, you only have to compute the solutions for at most k positive (non-zero)
integers with the remaining x_n all zero; the other solutions are merely
permutations of these. Indeed, you could narrow it further to descending
positive integers x_1 >= x_2 >= x_3 and so on; the remainder of the solutions
would be permutation of these.

--
.signature note: I am now avoiding replying to unclear or ambiguous postings.
Please review questions before posting them. Be specific. Use examples of what you mean,
of what you don't mean. Specify boundary conditions, and data classes and value
relationships -- what if we scrambled your data or used -Inf, NaN, or complex(rand,rand)?

The number of solutions for
n=6 and k=60 is 8259888

It is "reasonable" small.

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gelbfg$72h$1@fred.mathworks.com>...
> The number of solutions for n=6 and k=60 is 8259888
> It is "reasonable" small.
> Bruno

  In general the total number of solutions is (k+n-1)!/k!/(n-1)! .

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...

> In general the total number of solutions is (k+n-1)!/k!/(n-1)! .
>

Hi Roger,

what is your way to derive this formula ?

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gemb7o$hib$1@fred.mathworks.com>...
> "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...
> > In general the total number of solutions is (k+n-1)!/k!/(n-1)!

> Hi Roger,
> what is your way to derive this formula ?
> Bruno

Hi Bruno,

  Probably the easiest way is to use mathematical induction. Let P(n) be the proposition that the number of solutions for n non-negative integers with a sum of k is equal to

 (k+n-1)!/k!/(n-1)!

for all non-negative integers k. It is obvious that this is true for n = 1 since there is clearly only one possible solution in that case. Suppose that it holds for n = N. Then we try to prove it for n = N+!. The value of the last (the N+1 st) term may be any integer value j from j = 0 to j = k. The remaining terms must then have a sum of k-j and by our inductive hypothesis there are

 (j+N-1)!/j!/(N-1)!

solutions for that j. The sum of all of these,

 sum, j = 0 to k, of (j+N-1)!/j!/(N-1)! ,

is identically equal to (k+N)!/k!/N! which proves P(N+1). This establishes the proposition P(n) for all integers n.

  This last sum equality is a known identity about the sum in a Pascal triangle along a diagonal and can be easily be proved using a further mathematical induction on k.

Roger Stafford

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <geni8e$ajn$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gemb7o$hib$1@fred.mathworks.com>...
> > "Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...
> > > In general the total number of solutions is (k+n-1)!/k!/(n-1)!
>
> > Hi Roger,
> > what is your way to derive this formula ?
> > Bruno
>
> Hi Bruno,
>
> Probably the easiest way is to use mathematical induction. Let P(n) be the proposition that the number of solutions for n non-negative integers with a sum of k is equal to
>
> (k+n-1)!/k!/(n-1)!
>
> for all non-negative integers k. It is obvious that this is true for n = 1 since there is clearly only one possible solution in that case. Suppose that it holds for n = N. Then we try to prove it for n = N+!. The value of the last (the N+1 st) term may be any integer value j from j = 0 to j = k. The remaining terms must then have a sum of k-j and by our inductive hypothesis there are
>
> (j+N-1)!/j!/(N-1)!
>
> solutions for that j. The sum of all of these,
>
> sum, j = 0 to k, of (j+N-1)!/j!/(N-1)! ,
>
> is identically equal to (k+N)!/k!/N! which proves P(N+1). This establishes the proposition P(n) for all integers n.
>
> This last sum equality is a known identity about the sum in a Pascal triangle along a diagonal and can be easily be proved using a further mathematical induction on k.
>

Thank you Roger. I didn't see it yesterday after a quick look. It's relatively straightforward to prove the formula after knowing it, but derive it requires some skill. Pretty.

Bruno

Thank you, Walter, Bruno, Roger! I understand better the problem now!!

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gel0b6$3li$1@fred.mathworks.com>...

>
> Have you check the number of solutions for large n? It might be not possible to compute.
>
> Here is code in FEX that can accomplish that, but again, try to look at the feasibility before solving: http://www.mathworks.com/matlabcentral/fileexchange/17818
>
> Bruno

Hi, Bruno,

Thank you for the help. Your subfunction v=allVL1eq(n, L1, head) works fine for my problem. But I have some difficulty in understanding the recursive algorithm. I know it does the job, and more or less how it works, but still feel confused about it. What is the basic idea of this recursive algorithm? would you like to explain a litle bit for me... Lots of thanks

/Oriole

"Roger Stafford" <ellieandrogerxyzzy@mindspring.com.invalid> wrote in message <gelf99$84m$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gelbfg$72h$1@fred.mathworks.com>...
> > The number of solutions for n=6 and k=60 is 8259888
> > It is "reasonable" small.
> > Bruno
>
> In general the total number of solutions is (k+n-1)!/k!/(n-1)! .
>
> Roger Stafford

Thank you Roger for the formula. It is vey useful..
/Oriole

"Oriole " <oriole_ni@hotmail.com> wrote in message <geqe85$chp$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gel0b6$3li$1@fred.mathworks.com>...
>
> >
> > Have you check the number of solutions for large n? It might be not possible to compute.
> >
> > Here is code in FEX that can accomplish that, but again, try to look at the feasibility before solving: http://www.mathworks.com/matlabcentral/fileexchange/17818
> >
> > Bruno
>
> Hi, Bruno,
>
> Thank you for the help. Your subfunction v=allVL1eq(n, L1, head) works fine for my problem. But I have some difficulty in understanding the recursive algorithm. I know it does the job, and more or less how it works, but still feel confused about it. What is the basic idea of this recursive algorithm? would you like to explain a litle bit for me... Lots of thanks
>
> /Oriole

You can look at my partitions function on the
file exchange. It is certainly less elegant than
Bruno's code as I recall, although it is still
recursive.

The idea behind these recursive methods to find
the partitions of the number k is to pick a value
for x1. Once you have done that, you are now
looking for all the partitions of k-x1. Repeat
recursively until done.

John

"Oriole " <oriole_ni@hotmail.com> wrote in message <geqe85$chp$1@fred.mathworks.com>...
> "Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <gel0b6$3li$1@fred.mathworks.com>...
>
> >
> > Have you check the number of solutions for large n? It might be not possible to compute.
> >
> > Here is code in FEX that can accomplish that, but again, try to look at the feasibility before solving: http://www.mathworks.com/matlabcentral/fileexchange/17818
> >
> > Bruno
>
> Hi, Bruno,
>
> Thank you for the help. Your subfunction v=allVL1eq(n, L1, head) works fine for my problem. But I have some difficulty in understanding the recursive algorithm. I know it does the job, and more or less how it works, but still feel confused about it. What is the basic idea of this recursive algorithm? would you like to explain a litle bit for me... Lots of thanks
>

Oh there is nothing very mysterious about it

Assume we want to look for the all combinations of (1)
x1 + x2 + ... + xn = k (eqt1)

Then what are the possible values for x1 ? Answer: It can take any value from 0, 1, 2, ... to k.

Now pick a fix value j for x1 : x1 = j.

For (eqt1) to be true; we need the rest to verifies:

x2 + x3 + .... + xn = k-j (eqt2)

(eqt2) is the same type as (eqt1) with one less variable. That gives the recursive relation, and it can goes down to the case with a single variable: the very last recursion reduces to
xn = somevalue. (eqt3)
The solution of that is trivial.

When you look at the engine "allVL1eq", you will see the first test "if n==1" treats (eqt3).

The second "else" branch loops over j=1... k and calls recursively to solve (eqt2), then add the head column "j" in front of the array of solutions ("if nargin>=3"). Finally all the array are concatenated using cell2mat(...).

Bruno

"Bruno Luong" <b.luong@fogale.findmycountry> wrote in message <geqgdi$crb$1@fred.mathworks.com>...
>
> Oh there is nothing very mysterious about it
>
> Assume we want to look for the all combinations of (1)
> x1 + x2 + ... + xn = k (eqt1)
>
> Then what are the possible values for x1 ? Answer: It can take any value from 0, 1, 2, ... to k.
>
> Now pick a fix value j for x1 : x1 = j.
>
> For (eqt1) to be true; we need the rest to verifies:
>
> x2 + x3 + .... + xn = k-j (eqt2)
>
> (eqt2) is the same type as (eqt1) with one less variable. That gives the recursive relation, and it can goes down to the case with a single variable: the very last recursion reduces to
> xn = somevalue. (eqt3)
> The solution of that is trivial.
>
> When you look at the engine "allVL1eq", you will see the first test "if n==1" treats (eqt3).
>
> The second "else" branch loops over j=1... k and calls recursively to solve (eqt2), then add the head column "j" in front of the array of solutions ("if nargin>=3"). Finally all the array are concatenated using cell2mat(...).
>
> Bruno

Thank you Bruno, elegant explaination, I got it now.
/Oriole

"John D'Errico" <woodchips@rochester.rr.com> wrote in message <geqeuo$m4e$1@fred.mathworks.com>...
> You can look at my partitions function on the
> file exchange. It is certainly less elegant than
> Bruno's code as I recall, although it is still
> recursive.
>
> The idea behind these recursive methods to find
> the partitions of the number k is to pick a value
> for x1. Once you have done that, you are now
> looking for all the partitions of k-x1. Repeat
> recursively until done.
>
> John

Thank you John, now I know that the process is called integer partition. I was wondering before what it is called, have never studied Number theory.. hehe.. I understand also what exactly is a recursive algorithm now..thank you for your explaination.