Combinations - nCr << Back

Take a look at this problem. The goal is to find out all possible combination within a sequence of numbers. Let's think of the Lottery - there are 54 possible numbers, however only 6 numbers are drawn. The sequence of the numbers doesn't matter (otherwise we would be calculating permutation instead of combination). The number of combination is basically 54C6. Let's say you are to write a program to print out all possible combination of the tickets. How would you do it?

Another example would be that you are evaluating a Texas Hold'em game, where each player is holding 2 cards and there are 5 community cards out there. To calculate the number of combination is simple - simply just do 7C5, which will yield 21 (there are 21 possible 5-card hands). Let's say you are to write a program to print out all possible hands for each player. How would you do it?

Recursive programming comes to the rescue. The PrintLoop procedure is called when a combination is found.

Use UI

Procedure PrintLoop Integer[] ByRef loopCounters Integer r
	Integer nIndex
	Decrement r
	For nIndex From 0 to r
		Show loopCounters[nIndex] " "

Procedure nCrInner Integer[] ByRef loopCounters Integer nPos Integer n Integer r
	If (nPos >= r) Procedure_Return
	Move (If(nPos = 0, 0, loopCounters[nPos - 1] + 1)) to loopCounters[nPos]
	While (loopCounters[nPos] < n)
		If (nPos = r - 1) Send PrintLoop (&loopCounters) r
		Send nCrInner (&loopCounters) (nPos + 1) n r
		Increment loopCounters[nPos]

Procedure nCr Integer n Integer r
	Integer[r] loopCounters
	Send nCrInner (&loopCounters) 0 n r

Send nCr 7 5
InKey FieldIndex

Free Web Hosting