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.

Jerry McManus is a freelance Lingo programmer, working and living in Seattle. His love of computer gaming led him to begin his career at Electronic Arts in 1992, eventually working his way up to lead developer on CD-ROM projects beginning with Director 3.0. A recent casualty of The Great Dot Com Crash, Jerry can be found at home working feverishly on any one of several projects including games, books, websites, portfolios, 3d graphics, animations, and a wide variety of other things that somehow never quite seem to get finished...