title: Generating all 5 card poker hands
body: <p>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.</p>
  
  <p>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 <a href="http://en.wikipedia.org/wiki/Poker_probability" rel="noreferrer">wikipedia</a>, there are 134,459 distinct 5 card hands once you account for possible suit recolorings.</p>
  
  <p>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:</p>
  
  <pre><code># 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] &amp; 3
      if suit_map[suit] is None:
        suit_map[suit] = next_suit
        next_suit += 1
      hand[i] = hand[i] &amp; ~3 | suit_map[suit]
    return hand
  
  def expand_hand(hand, min_card):
    used_map = 0
    for card in hand:
      used_map |= 1 &lt;&lt; card
  
    hands = set()
    for card in range(min_card, 52):
      if (1 &lt;&lt; card) &amp; 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 &gt; 0 else 0
        new_hands.update(expand_hand(hand, min_card))
      hands = new_hands
    return hands
  </code></pre>
  
  <p>Unfortunately, this generates too many hands:</p>
  
  <pre><code>&gt;&gt;&gt; len(expand_hands(set([()]), 5))
  160537
  </code></pre>
  
  <p>Can anyone suggest a better way to generate just the distinct hands, or point out where I've gone wrong in my attempt?</p>