Path: news.mathworks.com!not-for-mail
From: <HIDDEN>
Newsgroups: comp.soft-sys.matlab
Subject: Re: How can I do this in MATLAB? (Possibilities)
Date: Sat, 31 Jan 2009 20:25:03 +0000 (UTC)
Organization: The MathWorks, Inc.
Lines: 13
Message-ID: <gm2c2v$t90$1@fred.mathworks.com>
References: <gm1mkl$eq0$1@fred.mathworks.com> <gm1prp$95f$1@fred.mathworks.com> <gm1rrh$f6e$1@fred.mathworks.com> <gm1t2t$3eh$1@fred.mathworks.com> <gm1u0v$3df$1@fred.mathworks.com> <gm1uut$335$1@fred.mathworks.com>
Reply-To: <HIDDEN>
NNTP-Posting-Host: webapp-03-blr.mathworks.com
Content-Type: text/plain; charset="ISO-8859-1"
Content-Transfer-Encoding: 8bit
X-Trace: fred.mathworks.com 1233433503 29984 172.30.248.38 (31 Jan 2009 20:25:03 GMT)
X-Complaints-To: news@mathworks.com
NNTP-Posting-Date: Sat, 31 Jan 2009 20:25:03 +0000 (UTC)
X-Newsreader: MATLAB Central Newsreader 1187260
Xref: news.mathworks.com comp.soft-sys.matlab:515184


"Husam Aldahiyat" <numandina@gmail.com> wrote in message <gm1uut$335$1@fred.mathworks.com>...
> Amazing. I can't believe you write codes from your mind without testing them.
> This is what I was *really* looking for, thanks!

  Sorry about that, Husam!  (Blush!)

  To compensate for that, I will expound on the theoretical aspects of that algorithm.  Is is fairly easy to show that for each one of the combinations churned out by nchoosek(1:m+n,n), provided it is in ascending order (which obviously it can be placed in by 'sort' if necessary,) the processing with the 'diff' and subtraction by 1, maps each combination uniquely onto one of your number sets.  A different combination must necessarily lead to a different number set.

  On the other hand, if you add 1 to any of your number sets, and then do a 'cumsum', you are bound to arrive back at a unique combination of ascending numbers from 1:m+n.  A different number set will always lead to a different subsequence of 1:m+n - that is to say, a combination which is in ascending order.  Since this is the inverse of the "diff" mapping, this shows that we have a one-to-one mapping of all combinations onto all of your kind of sets for any given m and n.

  That establishes the validity of the algorithm and the fact that there are exactly (m+n)!/(n!*m!) of your different number sets.

Roger Stafford