#
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 _{54}C_{6}. 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 _{7}C_{5},
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