Path: news.mathworks.com!not-for-mail
From: "Bruno Luong" <b.luong@fogale.findmycountry>
Newsgroups: comp.soft-sys.matlab
Subject: Re: integer solutions for x_1+x_2+...+x_n = k
Date: Tue, 4 Nov 2008 21:56:02 +0000 (UTC)
Organization: FOGALE nanotech
Lines: 38
Message-ID: <geqgdi$crb$1@fred.mathworks.com>
References: <geku21$eku$1@fred.mathworks.com> <gel0b6$3li$1@fred.mathworks.com> <geqe85$chp$1@fred.mathworks.com>
Reply-To: "Bruno Luong" <b.luong@fogale.findmycountry>
NNTP-Posting-Host: webapp-05-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1225835762 13163 172.30.248.35 (4 Nov 2008 21:56:02 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Tue, 4 Nov 2008 21:56:02 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 390839
Xref: news.mathworks.com comp.soft-sys.matlab:498960


"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