Generating all 5 card poker hands

Question

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?

Answer 1

Generating equivalence classes for 5 card hands is not an easy task. When I need this I usually use the http://www.vpgenius.com/ webpage. At http://www.vpgenius.com/video-poker/games/ you can choose which variety of poker game you need, and in the "Programming tab" you have an section on "Unique Suit Patterns". So just copying that and loading into program might be easier than trying to generate your own.

Answer 2

Take a look here:

http://specialk-coding.blogspot.com/

http://code.google.com/p/specialkpokereval/

These regard a 5-card hand (and a 7-card hand) as an integer, the sum the individual cards, which is independent of the suit. Exactly what you need.

This is part of a scheme for quickly ranking 7- and 5-card hands, written in Objective-C and Java.

Answer 3

Your overall approach is sound. I'm pretty sure the problem lies with your make_canonical function. You can try printing out the hands with num_cards set to 3 or 4 and look for equivalencies that you've missed.

I found one, but there may be more:

# The inputs are equivalent and should return the same value
print make_canonical([8, 12 | 1]) # returns [8, 13]
print make_canonical([12, 8 | 1]) # returns [12, 9]

For reference, below is my solution (developed prior to looking at your solution). I used a depth-first search instead of a breadth-first search. Also, instead of writing a function to transform a hand to canonical form, I wrote a function to check if a hand is canonical. If it's not canonical, I skip it. I defined rank = card % 13 and suit = card / 13. None of those differences are important.

import collections

def canonical(cards):
    """
    Rules for a canonical hand:
    1. The cards are in sorted order

    2. The i-th suit must have at least many cards as all later suits.  If a
       suit isn't present, it counts as having 0 cards.

    3. If two suits have the same number of cards, the ranks in the first suit
       must be lower or equal lexicographically (e.g., [1, 3] <= [2, 4]).

    4. Must be a valid hand (no duplicate cards)
    """

    if sorted(cards) != cards:
        return False
    by_suits = collections.defaultdict(list)
    for suit in range(0, 52, 13):
        by_suits[suit] = [card%13 for card in cards if suit <= card < suit+13]
        if len(set(by_suits[suit])) != len(by_suits[suit]):
            return False
    for suit in range(13, 52, 13):
        suit1 = by_suits[suit-13]
        suit2 = by_suits[suit]
        if not suit2: continue
        if len(suit1) < len(suit2):
            return False
        if len(suit1) == len(suit2) and suit1 > suit2:
            return False
    return True

def deal_cards(permutations, n, cards):
    if len(cards) == n:
        permutations.append(list(cards))
        return
    start = 0
    if cards:
        start = max(cards) + 1
    for card in range(start, 52):
        cards.append(card)
        if canonical(cards):
            deal_cards(permutations, n, cards)
        del cards[-1]

def generate_permutations(n):
    permutations = []
    deal_cards(permutations, n, [])
    return permutations

for cards in generate_permutations(5):
    print cards

It generates the correct number of permutations:

Cashew:~/$ python2.6 /tmp/cards.py | wc
134459

Answer 4

If you are just interested in hands that result in different hand rankings, there are actually only 7462 distinct hand classes that have to be considered (see Wikipedia).

By creating a table with an example for each class and their accompanying multiplicity you can check all relevant hands weighted with their probability quite fast. That is, assuming that no cards are known and therefore fixed beforehand already.

Answer 5

Chances are you really want to generate the number of distinct hands, in the sense of non-equivalent. In that case, according to the wikipedia article there are 7462 possible hands. Here is a python snippet that will enumerate them all.

The logic is simple: there is one hand for each 5-set of ranks; in addition, if all the ranks are distinct, another, different kind of hand can be formed by making all the suits match.

count = 0 

for i in range(0,13):
    for j in range (i,13):
        for k in range(j,13):
            for l in range(k,13):
                for m in range(l,13):
                    d = len(set([i,j,k,l,m])) # number of distinct ranks
                    if d == 1: continue    # reject nonsensical 5-of-a-kind
                    count += 1
                    # if all the ranks are distinct then 
                    # count another hand with all suits equal
                    if d == 5: count += 1

print count   # 7462

Answer 6

Here's a Python solution that makes use of numpy and generates the canonical deals as well as their multiplicity. I use Python's itertools module to create all 24 possible permutations of 4 suits and then to iterate over all 2,598,960 possible 5-card deals. Each deal is permuted and converted to a canonical id in just 5 lines. It's quite fast as the loop only goes through 10 iterations to cover all deals and is only needed to manage the memory requirements. All the heavy lifting is done efficiently in numpy except for the use of itertools.combinations. It's a shame this is not supportedly directly in numpy.

import numpy as np
import itertools

# all 24 permutations of 4 items
s4 = np.fromiter(itertools.permutations(range(4)), dtype='i,i,i,i').view('i').reshape(-1,4)

c_52_5 = 2598960 # = binomial(52,5) : the number of 5-card deals in ascending card-value order
block_n = c_52_5/10
def all5CardDeals():
    '''iterate over all possible 5-card deals in 10 blocks of 259896 deals each'''
    combos = itertools.combinations(range(52),5)
    for i in range(0, c_52_5, block_n):
        yield np.fromiter(combos, dtype='i,i,i,i,i', count=block_n).view('i').reshape(-1,5)

canon_id = np.empty(c_52_5, dtype='i')
# process all possible deals block-wise.
for i, block in enumerate(all5CardDeals()):
    rank, suit = block/4, block%4     # extract the rank and suit of each card
    d = rank[None,...]*4 + s4[:,suit] # generate all 24 permutations of the suits
    d.sort(2)                         # re-sort into ascending card-value order
    # convert each deal into a unique integer id
    deal_id = d[...,0]+52*(d[...,1]+52*(d[...,2]+52*(d[...,3]+52*d[...,4])))
    # arbitrarily select the smallest such id as the canonical one 
    canon_id[i*block_n:(i+1)*block_n] = deal_id.min(0)
# find the unique canonical deal ids and the index into this list for each enumerated hand
unique_id, indices = np.unique(canon_id, return_inverse=True)
print len(unique_id) # = 134459
multiplicity = np.bincount(indices)
print multiplicity.sum() # = 2598960 = c_52_5