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

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 2

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