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.

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

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: probability, combinatorics

30 comment(s)

Prefatory to the forthcoming (and ridiculously long) post on multiway equity computation with arbitrary hand distributions (random/ranged/specific) in poker.

James Devlin on Tuesday, March 31, 2009

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

D on Tuesday, March 31, 2009

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.

Ed K. on Tuesday, March 31, 2009

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.

Bill Mill on Tuesday, March 31, 2009

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.

Anonymous on Tuesday, March 31, 2009

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.

Kevin H on Tuesday, March 31, 2009

[i]>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:[/i]

Great catch. I have that check in C++, somehow it didn't make it in to the C# version. Bad programmer! "I must've put a decimal point in the wrong place or something..."

James Devlin on Tuesday, March 31, 2009

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.

Tim on Tuesday, March 31, 2009

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.

Anonymous on Tuesday, April 14, 2009

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 &gt;= 0; --j) {
    if (v[j] != (max + j - n))
        break;
}

if ((j &lt; 0) || (j &gt;= n)) {
    for (i = 0; i &lt; n; ++i)
        v[i] = i;
}
else if (j &lt; (n - 1)) {
    T dummy(v[j]);
    for (T k = j; k &lt; n; ++k)
        v[k] = dummy + k - j + 1;
}
else {
    ++v[j];
}

} [/quote]

Marc on Wednesday, April 15, 2009

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?"

Firesport on Saturday, April 18, 2009

Three words that may change your life.

"Enumerative combinatorics [using] matrices."

Orwellophile on Saturday, April 18, 2009

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.

Marc on Tuesday, April 21, 2009

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

supert on Monday, March 08, 2010

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

===

logo design & website design

Alex on Tuesday, June 22, 2010

nice article. keep post like this...

Fendi replica watches on Tuesday, July 20, 2010

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

Ayew on Wednesday, July 21, 2010

I loved this post so much. This was great. Keep it up!

Tudor replica watches on Saturday, July 24, 2010

PerformingGraham for sale that will create a one-wayswiss watches backlink to your website whichMaurice Lacroix watches is a good point to have. It is Patek Philippe watchesa time-consuming Tag Heuer for saleprocess even though it produces good outcomes U-boat for saleand works. You can also swiss watchespost comments on blogs alongMaurice Lacroix watches together with your link, but make sureGraham watches these blogs are do-follow, which dolce & gabbana handbagsindicates the link that youreplica coach handbags simply post will probably be replica handbagscounted by the search engines jimmy choo replicaas a backlink.There are many thingsversace replica handbags that contribute to online businessjuicy couture replica failure, and the lack of good action thomas wyldeis surely one of the deadliest business-killersdolce gabbana handbags on the net. Take action like by no means chloe handbags replicaprior to, and don’t get struck by analysis paralysisburberry replica. Your achievement lies in your rapid actionchanel replica and how well you apply numerous strategies.

replica watches on Saturday, July 24, 2010

nike air jordan 2010 nike air jordan 5 nike air jordan 3 nike air jordan 11 cheap nike air jordan 2 nike air jordan 1 nike air jordan shoes discount nike air jordan shoes nike air jordan 6 wholesale nike air jordan 1 discount nike air jordan 6 nike air jordan 7 nike air jordan 8 top quality nike air jordan shoes 23 nike air jordan 21 nike air jordan 22 nike air jordan 6 rings cheap nike air jordan 22 nike air lebron james shoes nike air lebron james shoes nike air jordan 2010 nike air joredan lebron james nike air jordan 2009 discount nike air jordan 2009 nike lebron james wholesale nike air jordan 2010 cheap nike air jordan 2009 discount nike air jordan 19 cheap nike air jordan 3 discount nike air jordan 18 brand nike air jordan 12 wholesale nike air jordan 2 nike air jordan 13 nike air jordan 14 nike air jordan 6 rings discount jordan shoes7 discount jordan shoes1 jordan shoes2010 jordan shoes 6 rings cheap jordan shoes2 discountjordan shoes3 discount jordan shoes4 jordan shoes uk23 jordan shoes classic bw22 cheap jordan shoes 21 ltd discount jordan shoes20 discountjordan shoes19 jordan shoes 18 uk nike air jordan shoes 17 cheap nike air jordan shoes 16 discount air jordan shoes 15 discount air jordan shoes 14 nike air jordan shoes 3 uk nike air jordan shoes 13 cheap nike air jordan shoes 11 discount air jordan shoes 6 discount jordan shoes 10 nike air jordan shoes 8 nike air jordan shoes 7 cheap louis vuitton bags cheap kobe bryant shoes cheap lebron james shoes .

cheapjordan on Saturday, July 24, 2010

I will keep visiting this blog very often. Blu ray ripper /

ipad converter on Sunday, July 25, 2010

ed hardy, cheap ed hardy, ed hardy clothing, ed hardy outlet, ed hardy jeans, ed hardy bags, ed hardy swimwear, ed hardy shirts, ed hardy tee, ed hardy caps, ed hardy purse, ed hardy board shorts, ed hardy shoes, ed hardy for men, ed hardy for women, ed hardy jeans for women.

cheap ed hardy on Tuesday, July 27, 2010

The house—which Hopper supposedly used to entertain his celebrity and artist pals like Jasper Johns and Roy Lichtenstein—features an open, loft-like floorplan, with soaring ceilings, exposed wood beams, and concrete floors that add to the masculine feel of the space.

ブランド腕時計;ロレックス時計;オメガ時計;IWC腕時計ロレックスデイトナ;ロレックスエクスプローラー;ロレックスGMTマスターII オメガスピードマスター;オメガシーマスター;オメガアクアテラ;オメガデ・ヴィル IWCアクアタイマー;IWCインヂュニア;IWCスピットファイアー;IWCポルトギーゼロレックスサブマリーナ;ロレックスヨットマスター;ロレックスターノグラフロレックスミルガウス;ロレックスエアキング;ロレックスパーペチュアルデイトロレックスチェリーニ　チェリニウム;ロレックスデイデイト;ロレックスプリンスオメガコンステレーション;IWCクラシックパイロット;IWCポートフィノ;ロレックスデイトジャスト

The furnishings are relatively few and far between, though not entirely minimalist: next to streamlined midcentury pieces there are also a number of exotic, elaborate-looking goods that look like they could have been picked up on Hopper’s travels (ornate Oriental rugs, earthy-looking carved wood tables).

バッグコピー、財布コピーグッチ;グッチバッグ;グッチコインケース・キーケース・ポーチ・小物;グッチ財布;シャネル;シャネルバッグ;シャネル財布;ベルト;グッチベルト;ルイ・ヴィトンベルト;エルメスベルト;シャネルベルト;フェンディベルト;バーバリーベルト;ディオールベルト;ブルガリベルト;ミュウミュウ;ミュウミュウバッグ;ミュウミュウ財布;プラダ;プラダバッグ;プラダ財布;バーバリー;バーバリーバッグ;バーバリー財布;バレンシアガ;バレンシアガバッグ;バレンシアガ財布;ディオール;ディオールバッグ ;ディオール財布;クロエ;クロエバッグ;クロエ財布;フェンディ;フェンディバッグ;フェンディ財布

And if all that space is too much for you, fear not: the main house and pool can be purchased separately (for $3.95 million!) while the condos range in price from $750,000 to $1.05 million.

グッチコピー|グッチバッグ|グッチ財布グッチハンドバッグ;グッチショルダーバッグ;グッチボストンバッグ;グッチトートバッグ; グッチ二ツ折り財布;グッチ長財布;グッチｗホック財布;

ブランド腕時計 on Wednesday, July 28, 2010

Best Louis vuitton online shop in www.sale4louisvuitton.com,you can buy New Louis vuitton bags and Prada handbags here. We also provide discount Louis vuitton

They call me the replica handbags guru; you name it Louis vuitton wallets, Chanel, Gucci, & Coach I love it. Join our community of replica lovers and stay informed

Louis vuitton Handbags - Instruments for professionals with Swiss chronograph ... Replica Louis vuitton online shop is a great ambassador of the brandname

louisvuitton4 on Thursday, July 29, 2010

best replica louis vuitton onlinein

www.sale4louisvuitton.com ,you can buy New Louis Vuitton outlet online here. We also provide discount

Buy Replica Louis Vuitton please come here, we are lowest price Louis Vuitton online Replica Watches,Best

Breitling,Rolex,Omega Replica Watch .

we offer cheap and best Louis Vuitton Belt. ... All Categories, Louis Vuitton outlet Stephen Sprouse Collection ...

Reviews and Articles on Top 10 Handbags Lists for Best Louis Vuitton,Louis Vuitton,Best Hermes.

louis vuitton on Thursday, July 29, 2010

carmi on Friday, July 30, 2010

essay essay writing essay writing service essay writing service uk

jane on Friday, July 30, 2010

Choosing the right tiffany jewelry accessory will turn an ordinary outfit into a fashion statement before you buy it from one mall or others, you can budget from our mall; christian louboutin as being beautiful and making us feel sexy Italian research has shown that a good pair of heels can help tone the body, condition muscles and improve the wearer's sex life, buy it please click the link; Look for ed hardy clothing, just click the link and you will have a great surprise; Finding beautiful cartier jewelry as gifts, we provide different styles for your reference; Choose the different links of london jewellery from our site, enjoy free and fast shopping worldwide; If you plan on shopping for NFL jerseys, you can purchase nfl jerseys online at our mall. We will do our best to serve for you. Welcome you！

tiffany jewelry on Friday, July 30, 2010

Replica miu miu handbags are not just beautiful and elegant, but it is also at excellent quality and similar design as the real. You will like it once you see it. Now attention please, at our shop, we are holding a promotion. You can buy replica miu miu bags of high quality with the lowest price. Meanwhile, miu miu handbags buying from here you can enjoy free and fast delivery shipping. Welcome to our shop!

miu miu bags on Friday, July 30, 2010

Yes! Leave a Comment. All fields are optional.

Subscribe to Coding the Wheel over email or through any RSS reader. Coding the Wheel has been published since 2008.

Visualizing the Internet (48)
SEO Packages wrote: Insightful, but the internet is a lot more difficult to portray imo.
1,326 (41)
SEO Packages wrote: So disco isn't dead yet?
Dartboard-Driven Design (52)
SEO Packages wrote: Hilarious, very creative but I wouldn't guide myself after that. 90% of the surface of my target ...
How to Display Integrated Digg.com Comments on Your Website (27)
SEO Packages wrote: Very useful article, thanks for the info
Using Internet Conveyor Belts to Drive Traffic to Your Site (23)
SEO Packages wrote: Very useful info here, I am in the SEO business myself and I've learned some now stuff from your ...
Summoning the Harry Potter MMORPG (1048)
James Lloyd wrote: Is this Real LOOKS F*ING AMAZING :) can't wait till it is made :D
The Great Poker Hand Evaluator Roundup (119)
Cheap UGG Boots wrote: fddddffffff
The Great Poker Hand Evaluator Roundup (119)
mbt kisumu white wrote: dddddddddd
The Great Poker Hand Evaluator Roundup (119)
Discount MBT Shoes wrote: mbt kisumu black sandal and mbt kisumu white ar hot saling now in our website. This Summer,the mbt ...
How I Built a Working Online Poker Bot, Part 3 (133)
mr.cool wrote: Hello! I find this review very interesting ！Vibram FiveFingers
A Circular Dilemma Concluded (39)
online bollywood movies wrote: It seeks to show how rarely needed a high voltage working environment in which candidates are difficult ...
How I Built a Working Online Poker Bot, Part 3 (133)
wewr wrote: [Replica Watches][1] [1]: http://superior-replica.com/"Replica Watches" ...
How I Built a Working Online Poker Bot, Part 3 (133)
wewr wrote: Sorry i not mean spam,...just like your article,...cheers [Replica Watches][1] [1]: http://www.superior-replica.com/"Replica ...
How I Built a Working Online Poker Bot, Part 3 (133)
wewr wrote: Vibram FiveFingers
How I Built a Working Online Poker Bot, Part 3 (133)
Replica Watches wrote: Replica Watches
How I Built a Working Online Poker Bot, Part 3 (133)
Replica Watches wrote: Yeah, after a study it more deeply, I know now.Replica Watches
How I Built a Working Online Poker Bot, Part 3 (133)
Replica Watches wrote: I had not understood the purpose of this article, but after a study it more deeply, I know now. Replica ...
How I Built a Working Online Poker Bot, Part 3 (133)
Replica Watches wrote: posts that are very evocative readers like me to understand more about what is contained in this article ...
How I Built a Working Online Poker Bot, Part 7: Extracting Text from 3rd-Party Applications (318)
window cleaning wrote: Great series and I enjoyed each article very much. I hope now you've got a whole batch of articles ...
How I Built a Working Online Poker Bot, Part 3 (133)
property management wrote: fat burning furnace scam or real.

Name:
Website:
Email: