# The Combination Generator: Producing Permutations for Fun and Profit

March 4, 2003
by Jerry McManus

While working on a card game recently I was presented with an interesting problem: How can I find all possible combinations of three cards in a hand that holds five cards? Fortunately, the answer was simple. This was a job for an algorithm.

#### The Algorithm

Algorithms are mathematical formulas that can provide useful solutions to everyday programming problems. Some common uses of algorithms are compressing images, sorting lists, and encrypting sensitive data, to name just a few.For our problem we are specifically interested in algorithms that can enumerate combinations, also known as combinatorics. Anyone with experience in genetic research, specifically recombinant DNA, will be familiar with these algorithms.

#### The Analysis

Before digging any deeper into the mathematics of combinatorics, let's take a moment to analyze the specific requirements of our program. As stated earlier we want to find all possible subsets of three cards in a hand of five cards. This gives us a good starting place because we can easily define the input of our program.

Inputs:
A list of cards
The length of the subset

The first thing we want to do with the list of cards is determine the total number of combinations, which we will then use as the basis for the repeat loop that actually generates the list of combinations. This gives us the two main methods that our program will need.

Methods:
Calculate total number of combinations
Generate combination list

And finally, the output of our program, which will be the actual list of combinations itself.

Output:
A list of combinations

#### The Code

Using this analysis we can begin coding our program. The first task at hand is to calculate the total number of combinations, which requires that we factor our list of cards and which, in turn, requires that we first calculate some factorials. The formula for calculating factorials is fairly straightforward, here is the method that we will use to do the calculations:

on mGetFactorial (me, num)

factorial = 1
repeat
with x = num down to 1
factorial = factorial * x
end
repeat
return factorial

end

Next, we can use the factorials to find the total number of combinations:

-->calculate factorials
listFactorial = me.mGetFactorial(pListCount)
subsetFactorial = me.mGetFactorial(pSubsetCount)
listMinusSubsetFactorial = me.mGetFactorial(pListCount - pSubsetCount)
-->calculate total permutations
pTotal = listFactorial / (subsetFactorial * (listMinusSubsetFactorial))
pNumLeft = pTotal

Now that we have the total number of combinations we can get to the meat of our program, the algorithm for generating the combinations. The process for generating the combinations can be roughly described in these steps:

1. Start with a subset of indices that point to the first three items in the list.
2. Systematically loop through the subset and increment the indices, based on the total number of items in the list and the number of items in the subset.Here is the method that generates the list of combinations:

on mGetCombination (me)

-->check for first iteration
if pNumLeft = pTotal then

-->first iteration, use current subset
pNumLeft = pNumLeft - 1

else

-->not first iteration, get new subset
x = pSubsetCount

-->systematically go through the current subset
-->and increment the indices
repeat
while pCurrentSubset[x] = pListCount - pSubsetCount + x
x = x - 1
end
repeat

pCurrentSubset[x] = pCurrentSubset[x] + 1

repeat
with y = (x + 1) to pSubsetCount
pCurrentSubset[y] = pCurrentSubset[x] + y - x
end
repeat

-->got new subset, one less to go
pNumLeft = pNumLeft - 1

end
if

end

You may have noticed at this point that we are not operating on the actual list of cards itself, but that we are generating lists of indices that point into the list of cards. This gives us great flexibility in that we can pass any kind of list to the generator, not just a list of cards, but it will require the additional step of looping through our combination list and building the final list of card combinations.

-->build combination from item list
combination = []
repeat
with x = 1 to pSubsetCount