Date: 6 Feb 1995 09:00:04 -0800
From: "George Frazier" <georgef@farallon.com>
Subject: RE: WANTED: C code for m choose n combinations
To: "Dave Rusin" <rusin@math.niu.edu>

Dave,

Thanks for kindly replying.  But I think (and please correct me if I'm wrong)
that you're confusing the combinations in a set of cardinality m where each
subset (or combination) has cardinality n with the cardinality of the set.
So 

m choose n = m!/etc.  probably is meant to be read
|(m choose n)| = m!/etc.

George
_______________________________________________________________________________

m choose n = m!/(n!.(m-n)!)=m.(m-1)....(m-n+1)/n!, so all you need is a
single loop:
C=1
for i from 1 to n, let
	C=C*(m+1-i)/i

A couple of practical matters:
1) first make sure  n<= m/2;  if not, it's easier to compute m choose n-m
(which is equal to m choose n)
2) at each stage of the computation, the  C  above should be an integer;
depending on the quality of your division routine you might want to round
off to keep errors from propagating.
3) the method above is the safest way to avoid overflow, which can indeed
be a problem with moderate size  m  and  n.  For n<= m/2, the numbers  C
computed above will steadily increase to the right value -- you'll get no
overflow unless the final answer is too big. Roughly speaking,
ln( m choose n) = (m+1/2) ln(m) - (n+1/2) ln(n) - (n-m+1/2) ln(n-m) -0.92
from which you can estimate the worst-case scenario (which, if n  is 
unrestricted, will occur with  n = m/2).

dave

==============================================================================

Date: Mon, 6 Feb 95 11:15:30 CST
From: rusin (Dave Rusin)
To: georgef@farallon.com, rusin@math.niu.edu
Subject: RE: WANTED: C code for m choose n combinations

Ah, yes, sorry; a clash of terminology.

I haven't written  C  code in a few years; here's something Pascal-like

type list=array[1..100] of integer;

procedure fred(a, b:list; alen, blen, n: integer);
{*write out a subset including all of  a  and  n  elements of  b*}
var i,j:integer;
    c,d:list;

begin
	if n=0 then begin
		for i:=1 to alen do write(a[i]);
		writeln;
		end;
	if n>0 then begin
		for i:=1 to alen do c[i]:=a[i];
		for i:=1 to blen-n+1 do begin
			c[alen+1]:=b[i];
			for j:=1 to blen-i do d[j]:=b[j+i];
			fred(c, d, alen+1, blen-i, n-1);
{*in other words, take what you had in  a,  pick any element in  b  and
add it in to  a, then repeat the process using any subset of  b  containing
only elements further on in the list. This "only" stuff will ensure no
repitition*}
			end;
		end;
end;


Of course  (especially if you're using  C) it's probably better to use
pointers rather than recopying long lists, but that's a computer scientist's
problem, not a mathematician's!  :-)

dave