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 ₅₄C₆. 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 ₇C₅, 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] " "
	Loop
	Showln
End_Procedure 

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]
	Loop
End_Procedure

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

Send nCr 7 5
InKey FieldIndex