Re: COMBIN

[Erich Neuwirth <erich neuwirth univie ac at>]

An algorithm which could easily implemented as a worksheet function is the following:

How to compute the lexicographically next combination from a given combination
(k taken from n):
a) If the rightmost number in the row is  less than n, create a new combination
keeping all the numbers to the left of it and increasing the rightmost number by 1.
b) If the rightmost number is n, search the rightmost number whose right neighbor
is at least this number + 2. Increase this number by 1 and complete the row by 
number+2, number+3 until you have a row with k numbers.
If no such number exists, there is no next combination.

Start with 1,2,3..k and compute the next combination for each combination

Example (3 out of 5)

1,2,3: 3<5, therefore rule a applies, next is 1,2,4
1,2,4: 4<5, therefore rule a applies, next is 1,2,5
1,2,5: apply rule b). 2<5, therefore 2 can be increased, next is 1,3,4

3,4,5
No way of creating a next combination, so this is the last one.










On Jul 31, 2010, at 3:31 PM, Prof. John C Nash wrote:

> Slightly off-gnumeric, R (www.r-project.org) with which Gnumeric has had friendly exchanges, can do the job:
>
> > combn(5,2)
>     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
> [1,]    1    1    1    1    2    2    2    3    3     4
> [2,]    2    3    4    5    3    4    5    4    5     5
> >
>
> In the past there were some ways to call R from Gnumeric, but I fear they are not currently functional, buy 
> welcome correction on that.
>
> John Nash
>
> On 10-07-31 08:00 AM, gnumeric-list-request gnome org wrote:
> > Date: Fri, 30 Jul 2010 11:02:35 -0400
> > From: Morten Welinder<mortenw gnome org>
> > To: yannis yannis<yanniscfu gmail com>
> > Cc: gnumeric-list gnome org
> > Subject: Re: COMBIN
> > Message-ID:
> >      <AANLkTindhzApAg5ROvvxX4oJea5BZeT9zMprp3G6CuF- mail gmail com>
> > Content-Type: text/plain; charset=ISO-8859-1
> >
> > > Is there any way to know which are these combinations?
> > > Any advise could be very helpful. Thank you for your time!
> >
> > Not via Gnumeric, but http://en.wikipedia.org/wiki/Combination
> > is a good start.  Note the first external reference:
> > http://compprog.wordpress.com/2007/10/17/generating-combinations-1/
> >
> > Morten
> _______________________________________________
> gnumeric-list mailing list
> gnumeric-list gnome org
> http://mail.gnome.org/mailman/listinfo/gnumeric-list

--
Erich Neuwirth, University of Vienna
Faculty of Computer Science
Center for Computer Science Didactics and Learning Research 
Visit our SunSITE at http://sunsite.univie.ac.at
Phone: +43-1-4277-39902 Fax: +43-1-4277-39459