Generating all 5 card poker hands

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 valueprint 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 collectionsdef 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 Truedef 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 permutationsfor cards in generate_permutations(5):    print cards

It generates the correct number of permutations:

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

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 npimport itertools# all 24 permutations of 4 itemss4 = 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 orderblock_n = c_52_5/10def 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 handunique_id, indices = np.unique(canon_id, return_inverse=True)print len(unique_id) # = 134459multiplicity = np.bincount(indices)print multiplicity.sum() # = 2598960 = c_52_5

Your problem sounded interesting, so i simple tried to implements it by just looping over all possible hands in a sorted way. I've not looked at your code in details, but it seems my implementation is quite different from yours. Guess what count of hands my script found: 160537

• My hands are always sorted, e.g. 2 3 4 4 D
• If there are 2 equal cards, the color is also sorted (colors are just called 0,1,2,3)
• the first card has always color 0, the second color 0 or 1
• A card can only have the color of an previous card or the next bigger number, e.g. if card 1+2 have color 0, card three can only have the colors 0 or 1

Are you sure, the number on wikipedia is correct?

count = 0for a1 in range(13):    c1 = 0    for a2 in range(a1, 13):        for c2 in range(2):            if a1==a2 and c1==c2:                continue            nc3 = 2 if c1==c2 else 3            for a3 in range(a2, 13):                for c3 in range(nc3):                    if (a1==a3 and c1>=c3) or (a2==a3 and c2>=c3):                        continue                    nc4 = nc3+1 if c3==nc3-1 else nc3                    for a4 in range(a3, 13):                        for c4 in range(nc4):                            if (a1==a4 and c1>=c4) or (a2==a4 and c2>=c4) or (a3==a4 and c3>=c4):                                continue                            nc5 = nc4+1 if (c4==nc4-1 and nc4!=4) else nc4                            for a5 in range(a4, 13):                                for c5 in range(nc5):                                    if (a1==a5 and c1>=c5) or (a2>=a5 and c2>=c5) or (a3==a5 and c3>=c5) or (a4==a5 and c4>=c5):                                        continue                                    #print([(a1,c1),(a2,c2),(a3,c3),(a4,c4),(a5,c5)])                                    count += 1print("result: ",count)