The ability to work with combinations and permutations is important if you do any sort of roll-your-own analysis for games such as poker or lottery. In fact, despite the wide availability of poker-and-probability-related tools, I find myself visiting the excellent mathsisfun.com Combinations and Permutations calculator at least a couple times a week:
Calculating combinations and permutations by hand is trivial, if you remember the formulas (I can never keep them straight).
| Is Order Important? | Is Repetition Allowed? | Formula | Description |
| YES | YES |  |
Permutations with repetition. |
| YES | NO |  |
Permutations without repetition. |
| NO | YES |  |
Combinations with repetition. |
| NO | NO |  |
Combinations without repetition. |
The formulas give the total number of ways R things can be selected from a group of N things, taking into account whether or not the order of things chosen is important and whether or not a given thing can be chosen more than once. Fine. But what if we want to examine each specific combination/permutation in code? In other words, what if we want to exhaustively enumerate all possible combinations/permutations?
The straightforward/naive approach (and the one used in poker-related code) is to use a nested loop structure containing one loop for each thing chosen. These nested loop structures follow a universal pattern:
- The number of loops will always equal R (the number of things chosen).
- The limit of each loop will always equal N (the number of things chosen from).
- The loop initializer will always determine both a) whether repetition is allowed and b) whether order is important.
This holds true regardless of the specific values of N and R, and regardless of whether repetition is allowed or whether ordering is important. To illustrate, let's examine the looping structures for a classic situation: choosing five cards from a 52-card deck. In the following examples, we'll represent a card as an integer with a value between 0 and 51. We'll examine the four combination/permutation counting scenarios listed above.
- Permutations with repetition
- Permutations without repetition
- Combinations with repetition
- Combinations without repetition
It should be mentioned that the four counting solutions can be generalized to a single recursive function. It should also be mentioned that there are some very clever ways of counting and visiting permutations. But typically in the game of poker you'll see hard-coded nested loops for N = 52. (The Great Poker Hand Evaluator Roundup has some examples in this format.)
Permutations with repetition
{
int totalOutcomesEnumerated = 0;
for (int card1 = 0; card1 < 52; card1++)
{
for (int card2 = 0; card2 < 52; card2++)
{
for (int card3 = 0; card3 < 52; card3++)
{
for (int card4 = 0; card4 < 52; card4++)
{
for (int card5 = 0; card5 < 52; card5++)
{
// Each iteration of this loop visits a single outcome
totalOutcomesEnumerated++;
}
}
}
}
}
}
Total five-card permutations enumerated with this loop: 380,204,032.
Permutations without repetition
{
int totalOutcomesEnumerated = 0;
for (int card1 = 0; card1 < 52; card1++)
{
for (int card2 = 0; card2 < 52; card2++)
{
if (card2 == card1) continue;
for (int card3 = 0; card3 < 52; card3++)
{
if (card3 == card2 || card3 == card1) continue;
for (int card4 = 0; card4 < 52; card4++)
{
if (card4 == card3 || card4 == card2 || card4 == card1) continue;
for (int card5 = 0; card5 < 52; card5++)
{
if (card5 == card4 || card5 == card3 || card5 == card2 || card5 == card1) continue;
// Each iteration of this loop visits a single outcome
totalOutcomesEnumerated++;
}
}
}
}
}
}
Total five-card permutations enumerated with this loop: 311,875,200.
Combinations with repetition
{
int totalOutcomesEnumerated = 0;
for (int card1 = 0; card1 < 52; card1++)
{
for (int card2 = card1; card2 < 52; card2++)
{
for (int card3 = card2; card3 < 52; card3++)
{
for (int card4 = card3; card4 < 52; card4++)
{
for (int card5 = card4; card5 < 52; card5++)
{
// Each iteration of this loop visits a single outcome
totalOutcomesEnumerated++;
}
}
}
}
}
}
Total five-card combinations enumerated with this loop: 3,819,816.
Combinations without repetition
{
int totalOutcomesEnumerated = 0;
for (int card1 = 0; card1 < 48; card1++)
{
for (int card2 = card1 + 1; card2 < 49; card2++)
{
for (int card3 = card2 + 1; card3 < 50; card3++)
{
for (int card4 = card3 + 1; card4 < 51; card4++)
{
for (int card5 = card4 + 1; card5 < 52; card5++)
{
// Each iteration of this loop visits a single outcome
totalOutcomesEnumerated++;
}
}
}
}
}
}
Total five-card combinations enumerated with this loop: 2,598,960.
Conclusion
The purpose of this post was not to explain how to programmatically count things in code! That subject has been covered repeatedly and well. Just for starters:
- CodeProject: Combinations in C++
- Scalable Permutations!
- CodeProject: Combinations, Permutations, and Variations Using C# Generics
- CodeProject: Combinatorial Algorithms in C#
- Calculating Permutations and Job Interview Questions
- Cut the Knot: Counting and List All Permutations
- C++'s next_permutation and prev_permutation
- Ben Bear's next_combination and prev_combination
- Boost's permutation_iterator
- Loopless Functional Algorithms (PDF)
- Knuth: Generating All Permutations (PDF)
- Knuth: Generating All Combinations (PDF)
Instead, I wanted to isolate the sort of hard-coded loop structures you're likely to stumble across in poker-related code specifically, and to talk about how minor changes in the nested loop structure allow us to express different counting paradigms (permutations vs. combinations, with and without repetition) which are useful in games of skill and chance.
Posted by James Devlin 14 comment(s)
