Subject: Re: CCL:Routine to derive combinations of r objects chosen from among n (LONG)

From: [email-masked] (Frits Daalmans)
Date: Thu, 19 Oct 95 13:19:36 +0200

Alex May wrote:

>	I'm looking for an algorithm which derives combinations of r objects 
>chosen from among n. For instance, with 3 objects A,B and C there are 3 
>combinations of pairs: AB,AC and BC. It seems to be a natural candidate 
>for recursion a la factorial... 
>
>	I don't want to reinvent the wheel (who does? ;-)) so does anybody have
>any suggestions? Incidentally, I don't have access to all 7 volumes of 
>Knuth's "The art of computer programming". 
>
>	Anyhow, I'll go back to being a lurker now...
>
Hello,

First a remark: smart of you to not re-invent the wheel. I did :-(

I once made just such a routine for a regression program I was working on.
You hopefully realize that, if n is big, the number of combinations grows
exponentially with each r that you explore?

I don't have access to Knuth's book either, but this is how I solved it:
please mention the name of this re-inventer of the wheel in your program 
if you use it :-) 

1) calculate (n over r), the binomial. Be careful to calculate it using
 long integer (in C), otherwise it will overflow and end up negative :-(
I used this routine, it will work for n and k not too big:

/* N over K = N! / (K! (N-K)! ) */
long
noverk (n, k)
     int n;
     int k;
{
  long nk = 1;
  int i;

  if ((k == 0) || (k == n))
    return (nk);
  if (k > n / 2)
    k = n - k;

  for (i = 0; i < k; i++)
    nk = nk * (n - i) / (i + 1);
  return (nk);
}

 This shows you how many combinations you will have to calculate, so you
can print a message "come back after coffee", "come back next week" or
"use a supercomputer for this" or "forget it". :-)

2) I used an array of short integers to represent the bitvector of the
"objects" used: 1 means present, 0 means not present.
e.g. if n = 5, k = 2 you could have vector '00101' meaning: try set {C,E}
You could save some space by using a binary representation but all the 
fuss of getting the bits flipped is not worth it IMHO.

It might be a good idea to change the algorithm so you also have rules
to never try a certain object, or to always use a certain object: this
is how I made the algorithm so now I have to "translate back" to the
simpler version.

main algorithm:

setup:
The first of the (n over k) bitvectors is the one with all-ones left
and all-zeroes right; so (n-k)* '1', (k)* '0',  '1..10..0'

make a loop over the (n over k) combinations
    do what you want with the current bitvector in your program
    3) increment the bitvector 
done.

3) incrementing the bitvector: I used a kind of Gray-code algorithm
with the following rules:

3a) if rightmost element = '0',
    flip the most right occuring pattern '10' to '01' 
    (so you must search from right to left)
    return (this flip is always successful)

3b) else, (this is harder)
    find rightmost pattern '10..01' by searching for '10' from right to left,
         flip the '10' to '01', and 
         shove all '1's occuring right of this new '01' pattern to the left:
         in a while loop (goto loop in Fortran) flip all '01' patterns found
         right of the new '01' to '10'; repeat until all done.
         now you have a pattern of the form 'xxxxx01..10..0'
    return

A simple example for two objects out of 4:
(4 over 2) = 6
nr. bitvector
 1  1100
 2  1010
 3  1001
 4  0110
 5  0101
 6  0011

Enjoy,
Frits

Disclaimer: This algorithm is probably well-documented somewhere, so if I 
infringe on somebody's copyright please notify me: 
I do not intend to do so, I posted this message only to be of some help. 
It would be better if somebody posted a reference to a good review of 
this problem, but in my ignorance of combinatorics I know of none.
This text is my own opinion, not necessarily my employer's.

Frits Daalmans
OIO Conformational Analysis
Gorlaeus Laboratoria
Leiden, The Netherlands
E-mail: [email-masked]
Tel: [+31] (0)71-5274505

> From [email-masked] Thu Oct 19 07:19:58 1995

Hello and sorry,

in my last mail the line:
The first of the (n over k) bitvectors is the one with all-ones left 
and all-zeroes right; so (n-k)*'1', (k)*'0', '1..10..0' should of course
read:
(k)*'1', (n-k)*'0',   '1..10..0'
                        k^  ^n-k

apologies,
Frits

Frits Daalmans
OIO Conformational Analysis
Gorlaeus Laboratoria
Leiden, The Netherlands
E-mail: [email-masked]
Tel: [+31] (0)71-5274505