Exhaustively Enumerating Combinations and Permutations in Code

Tuesday, March 31, 2009

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: 

Combinations and Permutations calculator (www.mathsisfun.com)

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.

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

void Enumerate5CardPermutationsWithRepetition()
{
    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

void Enumerate5CardPermutationsWithoutRepetition()
{
    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

void Enumerate5CardCombinationsWithRepetition()
{
    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

void Enumerate5CardCombinations()
{
    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:

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.

Tags: combinatorics, probability

21 comment(s)

This one is good (I did not know the Math is Fun site, great finding). Looking forward to reading the next one!

I have some similar code which I use in my bot to do "poor-mans" equity evaluation.

I hate the hard-coded nested loop approach as it just seems ugly but it performs the best.. What I didn't know is how similar the other loop structures were. That's also a great calculator you pointed out so kudos and thanks.

If you want to be studly, you should read [url=http://www.google.com/url?sa=U&start=1&q=http://www-cs-faculty.stanford.edu/~uno/fasc2b.ps.gz&ei=aGfSSdy3BpbqlQeg6-mIBw&sig2=ff0pV8XhZqJack-kjrnA4A&usg=AFQjCNF6MvIABJ7Ua4K9brr5G1l30s3Q]Knuth on permutations and combinations[/url].

I wrote a [url=http://github.com/llimllib/personal_code/blob/aa975c508208e69ea7429598e1b731ff42423c87/python/permutation/permute.py"]python file[/url] to test how fast a bunch of them are in python, where recursion isn't really possible. Debugging nonrecursive permutation algorithms is kind of twisted fun.

It may be worth mentioning that some standard libraries already provided some functions for a small subset of this. e.g. C++ provides nextpermutation and prevpermutation.

Incidentally, it isn't too hard to rewrite your recursive solution to an iterative solution, while still maintaining its flexibility. That should generally be preferred in an imperative language, I would think.

Great post, BTW.

Technically, your "Permutations without repetition" is correct in that it generates the correct count of elements, but not the right ones. It should be like this:

for (int card1 = 0; card1 < 52; card1++) { for (int card2 = 0; card2 < 52; card2++) { if (card2 == card1) continue; for ... } }

Likewise, your recursive part has the same problem.

If all you really want is the permutation counts, it's much better to just do the multiplication. And personally, I prefer passing the count as the return argument rather than as a reference, but to each his own.

In your "combinations without repetition", which is, after all, the poker part of this, the code as written ends up with a bunch of unexecuted for loops. Usually I write it as the first loop going from 0 to 47 (i.e. to <48), the second to card1 + 1 to <49, etc.

So I've just finished reading this post along with all the links at the bottom... who knew that counting combinations could be so complicated? I mean Knuth. By the time you start reading Knuth (and by the way the version you link to is the "uncorrected" Knuth, not sure if a better version is available online) it starts getting out of hand. I'll prefer the standard nested loop method for anything having to do with poker k thx bye.

Can anyone tell me if there is a problem with the following function? It seems to work for me, but I have the nagging feeling there are better ways to go about it...

Thanks, Marc.

[quote] template <class T> void nextcombination(T max, T * v, sizet n) { T i; for (i = 0; i < n; ++i) { if (v[i] != i) break; }

T j;
for (j = n - 1; j >= 0; --j) {
    if (v[j] != (max + j - n))
        break;
}
if ((j < 0) || (j >= n)) {
    for (i = 0; i < n; ++i)
        v[i] = i;
}
else if (j < (n - 1)) {
    T dummy(v[j]);
    for (T k = j; k < n; ++k)
        v[k] = dummy + k - j + 1;
}
else {
    ++v[j];
}

} [/quote]

Yes, it's a template. And templates are the devil's playthings. If they weren't good enough for Bjorn to include in the original language, I refuse to use them.

Anyways, since a loop (or any other exhaustive method I know of) can't enumerate and evaluate a complete set of boards for more than 1 unknown opponents, the whole things seems to be an intractable problem.

Interestingly, in the field of combinatorics, and combinatoric explosions - there is something called the "Curse of dimensionality."

"The curse of dimensionality is the problem caused by the exponential increase in volume associated with adding extra dimensions to a (mathematical) space."

I say this is interesting, no only because of the cool name — although that is mostly the reason — but also because it was a seven dimensional solution that gave us the 2+2 LUT.

The 2+2 LUT is an amazing thing... especially when you think if it as "only slightly slower than 7 nested for() loops".

The alternate analogy to James' chess-board description of LUT, is a multiplication table (or times-table as we called them at school).

To find 2 x 7, you go right 7, and up 2, and you intersect on 14.

With the 2+2 LUT, you then go up (3rd dimension) to 8, across into a 4th dimension for the 4th card, pop through another 3 dimensions, and get an answer.

This tells us a number of things:

a) The 2+2 LUT was developed by aliens who live in at least 8 dimensions

b) That intractable polynomial problem with réductible solution spaces (eg, 52525252525252) can sometimes be solved by leveraging the same cursed dimensionality that caused them.

c) The LUT is a highly compacted map of the solution space, and may therefore hold the key (well, a map, or a subway token or somesuch) to enumerating non-unique combinations.

d) That I have wonder far off topic, and that my entire knowledge of this subject was gained from a 5 minute degree at Wikipedia.com.

While I am firmly off-track, it's worth mentioning that we all assume (for various reasons) that problems like this can only be solved by an exhaustive search. In fact, many enumeration problems in which the state space exhibits a sufficiently rich structure, can be efficiently solved with a reverse depth-first traversal.

I'm not quite sure what that means, because I just stole it from somebody elses web page, and he had a doctorate.

But it sure sounds cool.

I'm taking it to mean that if we want to exhaustively calculate a multiple player pre-flop scenario, we need to wait for even smarter aliens to give us 26 dimensional technology.

I do have suggestion, although it's not as good as my idea to wait for aliens. It's not mathematically accurate, but I think it's more correct in terms of game theory.

Only enumerate the flop.

Lets face it, if you have a pair of J's, and the flop comes AK7, you're going to fold faster than a piece of dough a pretzel factory as soon as someone bets into you. If it comes JxA, you're going to to either slow play or take down the pot, depending on possible flush/straight draws... if it comes 258, then all the math in the world isn't going to help you pick the perfect play.

Likewise, although the board may three-flush 12% of the time (I'm just making these numbers up), if only 1 of those cards comes on the flop, you'll most likely not be around to see the river. Same with straights.

I'd go a step further and say (IMNSHO), if I had a 26 dimensional alien LUT for instantaneous enumeration and evaluation of 9 players with unknown cards, or ranges of cards.... and all I had was a 5 card simulator that recognized a draw... I'd swap with you.

Even if I couldn't build another 5 card simulator, and even if I couldn't zap you with my alien phaser and then have both.

SCENE CUT: FAMILY GUY. Stewie is at a baseball game, he offers to swap his giant popcorn to the kid next to him, in exchange for a baseball bat. He gives the popcorn, takes the baseball bat, then hits the kid in the head with it. "What you learned?"

Three words that may change your life.

"Enumerative combinatorics [using] matrices."

Orwellophile,

I did the obvious and googled many, um, permutations of the above, together with "poker, evaluation" and other words. Didn't find anything that would allow me to bypass three months of hard work to apply it to poker. Any better hints?

Thanks, Marc.

Surely [quote] for (int c1=0;c1<5;c1++) { for (int c2=0;c2<c1;c2++) { for (int c3=0;c3<c2;c3++) {

        }
    }
}

[/quote] is better

great writing...I can understand easily what you have mentioned...Thanks for the post...

===

logo design & website design

Nice blog.... you can be a good writer rather..

It's a good article! so happy to read it!

Thank u so much dude for sharing your wonderful experiences with all of us.i am gonna come back again looking for some updates. interest rates calculator

Dsquared

You article also offers me good tips. I like reading here. adjustable beds

hello

actually i need (x,y) for 16 row and all combination without repeat for example we have 1- x /y y y
2-x /y x y 3-x /y x y 4-x /y x x and so on if you know any software to do like this please let me know

Thanks

Use the form below to leave a comment.






Coding the Wheel has appeared on the New York Time's Freakonomics blog, Jeff Atwood's Coding Horror, and the front page of Reddit, Slashdot, Digg.

On Twitter

Thanks for reading!

If you enjoyed this post, consider subscribing to Coding the Wheel by RSS or email. You can also follow us on Twitter and Facebook. And even if you didn't enjoy this post, better subscribe anyway. Keep an eye on us.

Question? Ask us.

About

Poker

Coding the Wheel =
Code, poker, technology, games, design, geekery.


Hire

You've read our technical articles, you've tolerated our rants and raves. Now you can hire us anytime, day or night, for any project large or small.

Learn more

We Like

Speculation, by Edmund Jorgensen.