I was reading http://en.wikipedia.org/wiki/Poker_probability which has a

good description of how to count the frequency of different types of

poker hands using a mathematical approach. A sample Python program is

given in the discussion page for doing it that way. I wanted to take a

different approach and actually generate all the possible hands,

counting the number of each type.

It's quite do-able on today's hardware, with 5-card (2,598,960

combinations) taking only one second and 7-card (133,784,560

combinations) taking around 60 seconds with my program on my notebook.

Does anyone have any suggestions for ways to improve my program,

especially about how to make it run faster? I'd like to get it down to

10 seconds or 5 seconds rather than 60, if that's possible. Profiling

suggests the vast majority of the run time is spent in the 'classify'

function.

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#include <assert.h>

#define N 7

/* N is the number of cards to deal. The best five-card poker hand

will be selected out of the N cards. Set N to 5 to get the

frequencies for 5-card poker hands as follows:

Straight flush 40

Four of a kind 624

Full house 3,744

Flush 5,108

Straight 10,200

Three of a kind 54,912

Two pair 123,552

One pair 1,098,240

No pair 1,302,540

Total 2,598,960

Or set N to 7 to get the frequences for 7-card poker hands

(as in Texas Hold'em) as follows:

Straight flush 41,584

Four of a kind 224,848

Full house 3,473,184

Flush 4,047,644

Straight 6,180,020

Three of a kind 6,461,620

Two pair 31,433,400

One pair 58,627,800

No pair 23,294,460

Total 133,784,560

Or set N to any other positive number and you should get

appropriate results, given enough time and as long as no

overflow occurs.

*/

#define RANK(card) ((card) % 13)

#define SUIT(card) ((card) / 13)

char *ranks[] = {"A", "2", "3", "4", "5", "6", "7", "8", "9", "T", "J",

"Q", "K"};

char *suits[] = {"S", "H", "D", "C"};

/* inc function increments hand to the next combination

of N cards from 52. If already at the last combination,

returns 1 to indicate end, otherwise returns 0.

Algorithm from nextComb function in combEnum.c at

http://reptar.uta.edu/NOTES5314/combEnum.c

*/

int inc(int *hand)

{

int i;

for(i = 0; i < N; i++)

{

if(hand[i] != 52 - N + i) break;

}

if(i == N) return 1;

for(i = N - 1; hand[i] == 52 - N + i; i--);

hand[i]++;

for(i++; i < N; i++)

hand[i] = hand[i - 1] + 1;

return 0;

}

enum class {

STRAIGHT_FLUSH,

FOUR,

FULL_HOUSE,

FLUSH,

STRAIGHT,

THREE,

TWO_PAIR,

ONE_PAIR,

NO_PAIR,

NUM_CLASSES

};

char *class_names[] = {

"Straight flush: ",

"Four of a kind: ",

"Full house: ",

"Flush: ",

"Straight: ",

"Three of a kind: ",

"Two Pair: ",

"One Pair: ",

"No Pair: "

};

void print_hand(int *hand, enum class cl)

{

int i;

for(i = 0; i < N; i++)

{

if(hand[i] < 0 || hand[i] >= 52)

printf("%d ", hand[i]);

else

printf("%s%s ", ranks[RANK(hand[i])], suits[SUIT(hand[i])]);

}

printf(" %s\n", class_names[cl]);

}

int comp(const void *v1, const void *v2)

{

const int *a = v1, *b = v2;

return *a < *b ? -1 : *a *b;

}

/* Even when there is both a straight and a flush in the cards,

they may not be over the same 5-card hand. This function

is called only when there is both a straight and a flush in

the cards, which is fairly rarely, to confirm whether or not

it is actually a straight flush. It operates by sorting the

cards in numerical order (which is suit-major, ensuring that

same-suited cards are together), then checking for a run of

5 adjacent cards each one greater than the last.

The variable 'state' represents the number of adjacent

straight-flush cards seen so far in the current run. It is

incremented when the current card is one greater than the

previous card, and of the same suit.

The hand is considered to contain a straight flush when state

reaches 4, or when state reaches 3 on a king and there is

an ace of the current suit.

*/

int confirm_straight_flush(int *hand)

{

int i, state = 0, tmp[N], hasAce[4] = {0, 0, 0, 0};

for(i = 0; i < N; i++)

{

if(RANK(hand[i]) == 0) hasAce[SUIT(hand[i])] = 1;

}

memcpy(tmp, hand, sizeof tmp);

qsort(tmp, N, sizeof *tmp, comp);

for(i = 1; i < N; i++)

{

if(( tmp[i] == tmp[i - 1] + 1

) && SUIT(tmp[i]) == SUIT(tmp[i - 1]))

{

state++;

}

else

{

state = 0;

}

if(state == 4 || (RANK(tmp[i]) == 12 && state == 3 &&

hasAce[SUIT(tmp[i])])) return 1;

}

return 0;

}

enum class classify(int *hand)

{

int rank_counts[13] = {0};

int suit_counts[4] = {0};

int i, flush = 0, straight = 0, state = 0;

int max_rank_count = 0, sub_rank_count = 0;

for(i = 0; i < N; i++)

{

rank_counts[RANK(hand[i])]++;

suit_counts[SUIT(hand[i])]++;

}

for(i = 0; i < 4; i++)

{

if(suit_counts[i] >= 5) flush = 1;

}

for(i = 0; i < 13; i++)

{

if(rank_counts[i] >= max_rank_count)

{

sub_rank_count = max_rank_count;

max_rank_count = rank_counts[i];

}

else if(rank_counts[i] >= sub_rank_count)

{

sub_rank_count = rank_counts[i];

}

if(rank_counts[i] != 0)

{

state++;

}

else

{

state = 0;

}

if(state == 5) straight = 1;

}

if(state == 4 && rank_counts[0] != 0) straight = 1; /* ace-high */

if(flush && straight && confirm_straight_flush(hand)) return

STRAIGHT_FLUSH;

if(max_rank_count >= 4) return FOUR;

if(max_rank_count == 3 && sub_rank_count >= 2) return FULL_HOUSE;

if(flush) return FLUSH;

if(straight) return STRAIGHT;

if(max_rank_count == 3) return THREE;

if(max_rank_count == 2 && sub_rank_count == 2) return TWO_PAIR;

if(max_rank_count == 2) return ONE_PAIR;

return NO_PAIR;

}

void print_counts(long long *counts)

{

int i;

long long total = 0;

for(i = 0; i < NUM_CLASSES; i++)

{

printf("%s%12lld\n", class_names[i], counts[i]);

total += counts[i];

}

printf("Total: %12lld\n", total);

}

int main(void)

{

int i;

long long counts[NUM_CLASSES] = {0};

int hand[N] = {0};

/* initialise hand to first combination */

for(i = 0; i < N; i++) hand[i] = i;

do

{

counts[classify(hand)]++;

} while(!inc(hand));

print_counts(counts);

return 0;

}

--

Simon.