Generating all 5 card poker hands

Viewed 12942

This problem sounds simple at first glance, but turns out to be a lot more complicated than it seems. It's got me stumped for the moment.

There are 52c5 = 2,598,960 ways to choose 5 cards from a 52 card deck. However, since suits are interchangeable in poker, many of these are equivalent - the hand 2H 2C 3H 3S 4D is equivalent to 2D 2S 3D 3C 4H - simply swap the suits around. According to wikipedia, there are 134,459 distinct 5 card hands once you account for possible suit recolorings.

The question is, how do we efficiently generate all these possible hands? I don't want to generate all hands, then eliminate duplicates, as I want to apply the problem to larger numbers of cards, and the number of hands to evaluate fast spirals out of control. My current attempts have centered around either generating depth-first, and keeping track of the currently generated cards to determine what suits and ranks are valid for the next card, or breadth-first, generating all possible next cards, then removing duplicates by converting each hand to a 'canonical' version by recoloring. Here's my attempt at a breadth-first solution, in Python:

# A card is represented by an integer. The low 2 bits represent the suit, while
# the remainder represent the rank.
suits = 'CDHS'
ranks = '23456789TJQKA'

def make_canonical(hand):
  suit_map = [None] * 4
  next_suit = 0
  for i in range(len(hand)):
    suit = hand[i] & 3
    if suit_map[suit] is None:
      suit_map[suit] = next_suit
      next_suit += 1
    hand[i] = hand[i] & ~3 | suit_map[suit]
  return hand

def expand_hand(hand, min_card):
  used_map = 0
  for card in hand:
    used_map |= 1 << card

  hands = set()
  for card in range(min_card, 52):
    if (1 << card) & used_map:
      continue
    new_hand = list(hand)
    new_hand.append(card)
    make_canonical(new_hand)
    hands.add(tuple(new_hand))
  return hands

def expand_hands(hands, num_cards):
  for i in range(num_cards):
    new_hands = set()
    for j, hand in enumerate(hands):
      min_card = hand[-1] + 1 if i > 0 else 0
      new_hands.update(expand_hand(hand, min_card))
    hands = new_hands
  return hands

Unfortunately, this generates too many hands:

>>> len(expand_hands(set([()]), 5))
160537

Can anyone suggest a better way to generate just the distinct hands, or point out where I've gone wrong in my attempt?

11 Answers

Here is a simple and straightforward algorithm for reducing hands to a canonical one based on suit permutatoins.

  1. convert hand to four bitsets, one per suit representing cards of the suit
  2. sort the bitsets
  3. convert bitsets back into hand

This is what the algorithm looks like in C++, with some implied Suit and CardSet classes. Note that the return statement converts the hand by concatenating the bitstrings.

CardSet CardSet::canonize () const
{
  int smasks[Suit::NUM_SUIT];
  int i=0;
  for (Suit s=Suit::begin(); s<Suit::end(); ++s)
    smasks[i++] = this->suitMask (s);

  sort (smasks, smasks+Suit::NUM_SUIT);

  return CardSet(
    static_cast<uint64_t>(smasks[3])                        |
    static_cast<uint64_t>(smasks[2]) << Rank::NUM_RANK      |
    static_cast<uint64_t>(smasks[1]) << Rank::NUM_RANK*2    |
    static_cast<uint64_t>(smasks[0]) << Rank::NUM_RANK*3);
}
Related