In the MOOC, Peter talks about algorithm P for shuffling.
Algorithm P is as follows:
import random
def shuffle(deck):
"Knuth's algorithm P."
N = len(deck)
for i in range(N-1):
swap(deck, i, random.randrange(i, N))
return deck
def swap(deck, i, j):
"Swap elements i and j in a collection."
#print('swap', i, j)
deck[i], deck[j] = deck[j], deck[i]
shuffle(list(range(1, 6)))
[4, 3, 2, 1, 5]
We can shuffle the same list many times and look at the distribution of values we arrive at.
vals = range(1, 6)
empty_dict = lambda : dict(zip(vals, [0]*len(vals)))
counts = dict(zip(vals, [empty_dict() for _ in vals]))
for n in range(10000):
deck = list(vals)
shuffle(deck)
for original, shuffled in zip(vals, deck):
counts[original][shuffled] += 1
counts
{1: {1: 2014, 2: 1932, 3: 2035, 4: 2033, 5: 1986}, 2: {1: 1927, 2: 2054, 3: 1945, 4: 1998, 5: 2076}, 3: {1: 2065, 2: 2029, 3: 1978, 4: 1977, 5: 1951}, 4: {1: 1962, 2: 2009, 3: 2046, 4: 1961, 5: 2022}, 5: {1: 2032, 2: 1976, 3: 1996, 4: 2031, 5: 1965}}
This seems quite nice: all values get assigned the same new value the same number of times. That's a good shuffle. What about the teacher's algorithm?
def shuffle1(deck):
"The teacher's algorithm."
N = len(deck)
swapped = [False] * N
while not all(swapped):
i, j = random.randrange(N), random.randrange(N)
swapped[i] = swapped[j] = True
swap(deck, i, j)
Let's benchmark this method now.
counts = dict(zip(vals, [empty_dict() for _ in vals]))
for n in range(10000):
deck = list(vals)
shuffle1(deck)
for original, shuffled in zip(vals, deck):
counts[original][shuffled] += 1
counts
{1: {1: 1342, 2: 2165, 3: 2206, 4: 2191, 5: 2096}, 2: {1: 2194, 2: 1371, 3: 2136, 4: 2116, 5: 2183}, 3: {1: 2169, 2: 2153, 3: 1326, 4: 2131, 5: 2221}, 4: {1: 2146, 2: 2094, 3: 2192, 4: 1384, 5: 2184}, 5: {1: 2149, 2: 2217, 3: 2140, 4: 2178, 5: 1316}}
import itertools
def best_wild_hand(hand):
"Try all values for jokers in all 5-card selections."
# isolate jokers
jokers = [card for card in hand if card[0] == "?"]
normal_cards = [card for card in hand if card[0] != "?"]
# replace jokers by their equivalent cards
hands = [normal_cards[:]]
# generate combinations
for joker in jokers:
joker_cards = [str(rank) + suit
for rank in [1, 2, 3, 4, 5, 6, 7, 8, 9, 'T', 'J', 'Q', 'K']
for suit in {'B': ['S', 'C'], 'R':['H', 'D']}[joker[1]]]
print(joker_cards)
for hand in hands:
for joker_card in joker_cards:
hands.append(hand[:] + [joker_card])
print(len(hands))
# keep best one
return max(itertools.combinations(hands, 5), key=hand_rank)
def test_best_wild_hand():
assert (sorted(best_wild_hand("6C 7C 8C 9C TC 5C ?B".split()))
== ['7C', '8C', '9C', 'JC', 'TC'])
assert (sorted(best_wild_hand("TD TC 5H 5C 7C ?R ?B".split()))
== ['7C', 'TC', 'TD', 'TH', 'TS'])
assert (sorted(best_wild_hand("JD TC TH 7C 7D 7S 7H".split()))
== ['7C', '7D', '7H', '7S', 'JD'])
return 'test_best_wild_hand passes'
#test_best_wild_hand()
best_wild_hand("6C 7C 8C 9C TC 5C ?B".split())
['1S', '1C', '2S', '2C', '3S', '3C', '4S', '4C', '5S', '5C', '6S', '6C', '7S', '7C', '8S', '8C', '9S', '9C', 'TS', 'TC', 'JS', 'JC', 'QS', 'QC', 'KS', 'KC']
--------------------------------------------------------------------------- KeyboardInterrupt Traceback (most recent call last) <ipython-input-11-1b7ae8cbc1af> in <module>() 31 32 #test_best_wild_hand() ---> 33 best_wild_hand("6C 7C 8C 9C TC 5C ?B".split()) <ipython-input-11-1b7ae8cbc1af> in best_wild_hand(hand) 16 for hand in hands: 17 for joker_card in joker_cards: ---> 18 hands.append(hand[:] + [joker_card]) 19 print(len(hands)) 20 # keep best one KeyboardInterrupt:
%debug
# CS 212, hw1-2: Jokers Wild
#
# -----------------
# User Instructions
#
# Write a function best_wild_hand(hand) that takes as
# input a 7-card hand and returns the best 5 card hand.
# In this problem, it is possible for a hand to include
# jokers. Jokers will be treated as 'wild cards' which
# can take any rank or suit of the same color. The
# black joker, '?B', can be used as any spade or club
# and the red joker, '?R', can be used as any heart
# or diamond.
#
# The itertools library may be helpful. Feel free to
# define multiple functions if it helps you solve the
# problem.
#
# -----------------
# Grading Notes
#
# Muliple correct answers will be accepted in cases
# where the best hand is ambiguous (for example, if
# you have 4 kings and 3 queens, there are three best
# hands: 4 kings along with any of the three queens).
import itertools
def best_wild_hand(hand):
"Try all values for jokers in all 5-card selections."
# isolate jokers
jokers = [card for card in hand if card[0] == "?"]
normal_cards = [card for card in hand if card[0] != "?"]
# replace jokers by their equivalent cards
joker_cards = itertools.product(*[possible_placeholders(joker) for joker in jokers])
# compute possible hands
possible_hands = itertools.combinations([normal_cards[:] + list(placeholder) for placeholder in joker_cards],
5)
return max(possible_hands, key=hand_rank)
def possible_placeholders(joker):
"Returns set of cards that a given joker can replace."
color = joker[1]
return [str(rank) + suit
for rank in [1, 2, 3, 4, 5, 6, 7, 8, 9, 'T', 'J', 'Q', 'K']
for suit in {'B': ['S', 'C'], 'R':['H', 'D']}[color]]
def test_best_wild_hand():
assert (sorted(best_wild_hand("TD TC 5H 5C 7C ?R ?B".split()))
== ['7C', 'TC', 'TD', 'TH', 'TS'])
assert (sorted(best_wild_hand("6C 7C 8C 9C TC 5C ?B".split()))
== ['7C', '8C', '9C', 'JC', 'TC'])
assert (sorted(best_wild_hand("JD TC TH 7C 7D 7S 7H".split()))
== ['7C', '7D', '7H', '7S', 'JD'])
return 'test_best_wild_hand passes'
# ------------------
# Provided Functions
#
# You may want to use some of the functions which
# you have already defined in the unit to write
# your best_hand function.
def hand_rank(hand):
"Return a value indicating the ranking of a hand."
ranks = card_ranks(hand)
if straight(ranks) and flush(hand):
return (8, max(ranks))
elif kind(4, ranks):
return (7, kind(4, ranks), kind(1, ranks))
elif kind(3, ranks) and kind(2, ranks):
return (6, kind(3, ranks), kind(2, ranks))
elif flush(hand):
return (5, ranks)
elif straight(ranks):
return (4, max(ranks))
elif kind(3, ranks):
return (3, kind(3, ranks), ranks)
elif two_pair(ranks):
return (2, two_pair(ranks), ranks)
elif kind(2, ranks):
return (1, kind(2, ranks), ranks)
else:
return (0, ranks)
def card_ranks(hand):
"Return a list of the ranks, sorted with higher first."
ranks = ['--23456789TJQKA'.index(r) for r, s in hand]
ranks.sort(reverse = True)
return [5, 4, 3, 2, 1] if (ranks == [14, 5, 4, 3, 2]) else ranks
def flush(hand):
"Return True if all the cards have the same suit."
suits = [s for r,s in hand]
return len(set(suits)) == 1
def straight(ranks):
"""Return True if the ordered
ranks form a 5-card straight."""
return (max(ranks)-min(ranks) == 4) and len(set(ranks)) == 5
def kind(n, ranks):
"""Return the first rank that this hand has
exactly n-of-a-kind of. Return None if there
is no n-of-a-kind in the hand."""
for r in ranks:
if ranks.count(r) == n: return r
return None
def two_pair(ranks):
"""If there are two pair here, return the two
ranks of the two pairs, else None."""
pair = kind(2, ranks)
lowpair = kind(2, list(reversed(ranks)))
if pair and lowpair != pair:
return (pair, lowpair)
else:
return None
#test_best_wild_hand()
best_wild_hand("TD TC 5H 5C 7C ?R ?B".split())
%debug
%debug