# 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:

- Start with a subset of indices that point to the first three items in the list.
- 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

combination.add (pItemList[pCurrentSubset[x]])

end repeat

And here is our finished combination generator:

This algorithm could find many interesting uses besides scoring card games. You could use it to generate combinations of lottery numbers, for example. There are also some challenging math puzzles that rely on enumerating combinations for their solutions, which could themselves be made into fun games, not to mention the possibilities for creating recombinant 'artificial life' programs. So there you have it, your very own combination generator. Enjoy producing permutations!

The sample movie above is available as a SIT or ZIP archive file.

Copyright 1997-2018, Director Online. Article content copyright by respective authors.