🚀 go-pugleaf

In article <1992Nov23.164311.27333@leland.Stanford.EDU>, spagiola@frinext.stanford.edu (Stefano Pagiola) writes:
|> William W. Plummer writes
|> >> Can someone provide me with an algorithm suitable for writing
|> >> a program to dump all possible combinations of 'n' elements
|> >> taken 'm' at a time?
|> > 
|> > n!/(m! * (n-m)!)
|> > 
|> > For instance in the MA Megabucks with 6 numbers out of 36 we have
|> > 
|> > 36!(6! * 30!)  =  36*35*34*33*32*31/(6*5*4*3*2*1)
|> > 		= 6*7*34*11*4*31
|> > 		= 1,947,792
|> 

|> Methinks the original poster wanted to _list_ all possible  
|> combinations, not just calculate how many there are...
|> 
I think your right. Let b(n,m)=n!/m!(n-m)!. 
Here's an informal description of a recursive solution:

1. If m=0 print nothing (empty set) and return.
2. If m = n print a list of all n elements and return. (this step is not needed
   but prevents a lot of extra function calls.)
3. If 0 < m < n do the following:
	a) Print all b(n-1,m-1) lists of m elements all
	   containing the n-th element.
	b) Print all b(n-1,m) lists of m elements NOT containing the n-th
	   element.
	c) return

This algorithm comes from the recursion formula: b(n,m)=b(n-1,m-1)+b(n-1,m).