如何找到在 Blackjack 中获得 21 的方法数？
How to find the number of ways to get 21 in Blackjack?
一些假设：
- 使用一副 52 张牌
- 图片卡计为 10
- A 算作 1 或 11
- 顺序并不重要（即 Ace + Queen 与 Queen + Ace 相同）
我想我会依次尝试所有可能的组合，看看哪些组合加起来是 21，但是混合卡片的方法太多了（52 种！方式）。这种方法也没有考虑到顺序并不重要，也没有考虑到任何一张牌最多只有 4 种类型（黑桃、梅花、方块、红桃）。
现在我在想这个问题：
我们有 11 个 "slots"。这些插槽中的每一个都可以有 53 种可能的东西：52 张卡片中的 1 张或根本没有卡片。之所以是 11 个插槽，是因为 11 张牌是可以发牌的最大数量，加起来仍然是 21；超过 11 张卡片加起来必须超过 21。
然后 "leftmost" 插槽将递增 1，并检查所有 11 个插槽是否加起来为 21（0 表示插槽中没有卡）。如果不是，则右边的下一个插槽将递增，然后是下一个，依此类推。
一旦前 4 个位置包含相同的 "card"（经过四次递增，前 4 个位置将全部为 1），第五个位置不能也是那个数字，因为有 4 个数字类型。第五个插槽将成为剩余可用卡中下一个最小的数字；在有四个 1 的情况下，第五个槽将变为 2，依此类推。
你会如何处理这个问题？
分而治之，利用以下知识：如果您有 13 张并选择 10 张，您只需选择卡片总和为 3 张即可查看...请注意，此解决方案可能很慢（大约需要 180 秒）在我的盒子上......它绝对不是最佳的）..
def sum_to(x,cards):
if x == 0: # if there is nothing left to sum to
yield []
for i in range(1,12): # for each point value 1..11 (inclusive)
if i > x: break # if i is bigger than whats left we are done
card_v = 11 if i == 1 else i
if card_v not in cards: continue # if there is no more of this card
new_deck = cards[:] # create a copy of hte deck (we do not want to modify the original)
if i == 1: # one is clearly an ace...
new_deck.remove(11)
else: # remove the value
new_deck.remove(i)
# on the recursive call we need to subtract our recent pick
for result in sum_to(x-i,new_deck):
yield [i] + result # append each further combination to our solutions
按如下方式设置您的卡片
deck = []
for i in range(2,11): # two through ten (with 4 of each)
deck.extend([i]*4)
deck.extend([10]*4) #jacks
deck.extend([10]*4) #queens
deck.extend([10]*4) #kings
deck.extend([11]*4) # Aces
然后调用你的函数
for combination in sum_to(21,deck):
print combination
不幸的是，这确实允许一些重复项潜入...
为了获得独特的条目，你需要稍微改变一下
在 sum_to 的最后一行将其更改为
# sort our solutions so we can later eliminate duplicates
yield sorted([i] + result) # append each further combination to our solutions
然后当你得到你的组合时，你必须做一些深暗的巫毒风格 python
unique_combinations = sorted(set(map(tuple,sum_to(21,deck))),key=len,reverse=0)
for combo in unique_combinations: print combo
从这个很酷的问题中我学到了以下内容（请记住，在真实游戏中你会让庄家和其他玩家也从同一副牌中移除）
there are 416 unique combinations of a deck of cards that make 21
there are 300433 non-unique combinations!!!
the longest number of ways to make 21 are as follows
with 11 cards there are 1 ways
[(1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3)]
with 10 cards there are 7 ways
with 9 cards there are 26 ways
with 8 cards there are 54 ways
with 7 cards there are 84 ways
with 6 cards there are 94 ways
with 5 cards there are 83 ways
with 4 cards there are 49 ways
with 3 cards there are 17 ways
with 2 cards there are 1 ways
[(10, 11)]
there are 54 ways in which all 4 aces are used in making 21!!
there are 106 ways of making 21 in which NO aces are used !!!
请记住，这些通常是次优玩法（即考虑 A,10 -> 1,10 并击中）
在担心花色和具有价值 10 的不同牌之前，让我们计算出有多少种不同的价值组合导致 21。例如 5, 5, 10, 1 就是这样一种组合。以下函数接受目标值 limit，表示可以选择的最低值的 start 和选择值列表的 used：
def combinations(limit, start, used):
# Base case
if limit == 0:
return 1
# Start iteration from lowest card to picked so far
# so that we're only going to pick cards 3 & 7 in order 3,7
res = 0
for i in range(start, min(12, limit + 1)):
# Aces are at index 1 no matter if value 11 or 1 is used
index = i if i != 11 else 1
# There are 16 cards with value of 10 (T, J, Q, K) and 4 with every
# other value
available = 16 if index == 10 else 4
if used[index] < available:
# Mark the card used and go through combinations starting from
# current card and limit lowered by the value
used[index] += 1
res += combinations(limit - i, i, used)
used[index] -= 1
return res
print combinations(21, 1, [0] * 11) # 416
由于我们对不同的卡片组合而不是不同的价值组合感兴趣，因此应将上面的基本情况修改为 return 可用于生成价值组合的不同卡片组合的数量。幸运的是，这是一项非常简单的任务，Binomial coefficient 可用于计算可以从 n 项中挑选出多少种不同的 k 项组合。
一旦知道 used 中每个值的不同卡片组合的数量，就可以将它们相互相乘以获得最终结果。因此，对于 5, 5, 10, 1 的示例，值 5 结果为 bcoef(4, 2) == 6，值 10 为 bcoef(16, 1) == 16，值 1 为 bcoef(4, 1) == 4。对于所有其他值 bcoef(x, 0) 结果为 1。将这些值相乘得到 6 * 16 * 4 == 384，然后 returned:
import operator
from math import factorial
def bcoef(n, k):
return factorial(n) / (factorial(k) * factorial(n - k))
def combinations(limit, start, used):
if limit == 0:
combs = (bcoef(4 if i != 10 else 16, x) for i, x in enumerate(used))
res = reduce(operator.mul, combs, 1)
return res
res = 0
for i in range(start, min(12, limit + 1)):
index = i if i != 11 else 1
available = 16 if index == 10 else 4
if used[index] < available:
used[index] += 1
res += combinations(limit - i, i, used)
used[index] -= 1
return res
print combinations(21, 1, [0] * 11) # 186184
所以我决定编写一个脚本，让每个可能的可行手牌都可以被检查。总数为 188052。由于我检查了所有可能的组合，因此这是确切的数字（而不是估计值）：
import itertools as it
big_list = []
def deck_set_up(m):
special = {8:'a23456789TJQK', 9:'a23456789', 10:'a2345678', 11:'a23'}
if m in special:
return [x+y for x,y in list(it.product(special[m], 'shdc'))]
else:
return [x+y for x,y in list(it.product('a23456789TJQKA', 'shdc'))]
deck_dict = {'as':1,'ah':1,'ad':1,'ac':1,
'2s':2,'2h':2,'2d':2,'2c':2,
'3s':3,'3h':3,'3d':3,'3c':3,
'4s':4,'4h':4,'4d':4,'4c':4,
'5s':5,'5h':5,'5d':5,'5c':5,
'6s':6,'6h':6,'6d':6,'6c':6,
'7s':7,'7h':7,'7d':7,'7c':7,
'8s':8,'8h':8,'8d':8,'8c':8,
'9s':9,'9h':9,'9d':9,'9c':9,
'Ts':10,'Th':10,'Td':10,'Tc':10,
'Js':10,'Jh':10,'Jd':10,'Jc':10,
'Qs':10,'Qh':10,'Qd':10,'Qc':10,
'Ks':10,'Kh':10,'Kd':10,'Kc':10,
'As':11,'Ah':11,'Ad':11,'Ac':11}
stop_here = {2:'As', 3:'8s', 4:'6s', 5:'4h', 6:'3c', 7:'3s', 8:'2h', 9:'2s', 10:'2s', 11:'2s'}
for n in range(2,12): # n is number of cards in the draw
combos = it.combinations(deck_set_up(n), n)
stop_point = stop_here[n]
while True:
try:
pick = combos.next()
except:
break
if pick[0] == stop_point:
break
if n < 8:
if len(set([item.upper() for item in pick])) != n:
continue
if sum([deck_dict[card] for card in pick]) == 21:
big_list.append(pick)
print n, len(big_list) # Total number hands that can equal 21 is 188052
在输出中，第一列是抽牌的张数，第二列是累计张数。因此，输出中“3”之后的数字是 2 张抽牌和 3 张抽牌的手牌总数，等于 21。小写字母 a 是低位 A（1 分），大写字母 A 是高位 A。我有一行（带有 set 命令的那一行），以确保它抛出任何有重复卡片的手。
该脚本需要 36 分钟才能 运行。因此，执行时间和准确性之间肯定存在权衡。 "big_list" 包含解决方案（即总和为 21 的每手牌）
>>>
================== RESTART: C:\Users\JBM\Desktop\bj3.py ==================
2 64
3 2100
4 14804
5 53296
6 111776
7 160132
8 182452
9 187616
10 188048
11 188052 # <-- This is the total count, as these numbers are cumulative
>>>
一些假设：
- 使用一副 52 张牌
- 图片卡计为 10
- A 算作 1 或 11
- 顺序并不重要（即 Ace + Queen 与 Queen + Ace 相同）
我想我会依次尝试所有可能的组合，看看哪些组合加起来是 21，但是混合卡片的方法太多了（52 种！方式）。这种方法也没有考虑到顺序并不重要，也没有考虑到任何一张牌最多只有 4 种类型（黑桃、梅花、方块、红桃）。
现在我在想这个问题：
我们有 11 个 "slots"。这些插槽中的每一个都可以有 53 种可能的东西：52 张卡片中的 1 张或根本没有卡片。之所以是 11 个插槽，是因为 11 张牌是可以发牌的最大数量，加起来仍然是 21；超过 11 张卡片加起来必须超过 21。
然后 "leftmost" 插槽将递增 1，并检查所有 11 个插槽是否加起来为 21（0 表示插槽中没有卡）。如果不是，则右边的下一个插槽将递增，然后是下一个，依此类推。
一旦前 4 个位置包含相同的 "card"（经过四次递增，前 4 个位置将全部为 1），第五个位置不能也是那个数字，因为有 4 个数字类型。第五个插槽将成为剩余可用卡中下一个最小的数字；在有四个 1 的情况下，第五个槽将变为 2，依此类推。
你会如何处理这个问题？
分而治之，利用以下知识：如果您有 13 张并选择 10 张，您只需选择卡片总和为 3 张即可查看...请注意，此解决方案可能很慢（大约需要 180 秒）在我的盒子上......它绝对不是最佳的）..
def sum_to(x,cards):
if x == 0: # if there is nothing left to sum to
yield []
for i in range(1,12): # for each point value 1..11 (inclusive)
if i > x: break # if i is bigger than whats left we are done
card_v = 11 if i == 1 else i
if card_v not in cards: continue # if there is no more of this card
new_deck = cards[:] # create a copy of hte deck (we do not want to modify the original)
if i == 1: # one is clearly an ace...
new_deck.remove(11)
else: # remove the value
new_deck.remove(i)
# on the recursive call we need to subtract our recent pick
for result in sum_to(x-i,new_deck):
yield [i] + result # append each further combination to our solutions
按如下方式设置您的卡片
deck = []
for i in range(2,11): # two through ten (with 4 of each)
deck.extend([i]*4)
deck.extend([10]*4) #jacks
deck.extend([10]*4) #queens
deck.extend([10]*4) #kings
deck.extend([11]*4) # Aces
然后调用你的函数
for combination in sum_to(21,deck):
print combination
不幸的是，这确实允许一些重复项潜入... 为了获得独特的条目，你需要稍微改变一下
在 sum_to 的最后一行将其更改为
# sort our solutions so we can later eliminate duplicates
yield sorted([i] + result) # append each further combination to our solutions
然后当你得到你的组合时，你必须做一些深暗的巫毒风格 python
unique_combinations = sorted(set(map(tuple,sum_to(21,deck))),key=len,reverse=0)
for combo in unique_combinations: print combo
从这个很酷的问题中我学到了以下内容（请记住，在真实游戏中你会让庄家和其他玩家也从同一副牌中移除）
there are 416 unique combinations of a deck of cards that make 21
there are 300433 non-unique combinations!!!
the longest number of ways to make 21 are as follows
with 11 cards there are 1 ways
[(1, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3)]
with 10 cards there are 7 ways
with 9 cards there are 26 ways
with 8 cards there are 54 ways
with 7 cards there are 84 ways
with 6 cards there are 94 ways
with 5 cards there are 83 ways
with 4 cards there are 49 ways
with 3 cards there are 17 ways
with 2 cards there are 1 ways
[(10, 11)]
there are 54 ways in which all 4 aces are used in making 21!!
there are 106 ways of making 21 in which NO aces are used !!!
请记住，这些通常是次优玩法（即考虑 A,10 -> 1,10 并击中）
在担心花色和具有价值 10 的不同牌之前，让我们计算出有多少种不同的价值组合导致 21。例如 5, 5, 10, 1 就是这样一种组合。以下函数接受目标值 limit，表示可以选择的最低值的 start 和选择值列表的 used：
def combinations(limit, start, used):
# Base case
if limit == 0:
return 1
# Start iteration from lowest card to picked so far
# so that we're only going to pick cards 3 & 7 in order 3,7
res = 0
for i in range(start, min(12, limit + 1)):
# Aces are at index 1 no matter if value 11 or 1 is used
index = i if i != 11 else 1
# There are 16 cards with value of 10 (T, J, Q, K) and 4 with every
# other value
available = 16 if index == 10 else 4
if used[index] < available:
# Mark the card used and go through combinations starting from
# current card and limit lowered by the value
used[index] += 1
res += combinations(limit - i, i, used)
used[index] -= 1
return res
print combinations(21, 1, [0] * 11) # 416
由于我们对不同的卡片组合而不是不同的价值组合感兴趣，因此应将上面的基本情况修改为 return 可用于生成价值组合的不同卡片组合的数量。幸运的是，这是一项非常简单的任务，Binomial coefficient 可用于计算可以从 n 项中挑选出多少种不同的 k 项组合。
一旦知道 used 中每个值的不同卡片组合的数量，就可以将它们相互相乘以获得最终结果。因此，对于 5, 5, 10, 1 的示例，值 5 结果为 bcoef(4, 2) == 6，值 10 为 bcoef(16, 1) == 16，值 1 为 bcoef(4, 1) == 4。对于所有其他值 bcoef(x, 0) 结果为 1。将这些值相乘得到 6 * 16 * 4 == 384，然后 returned:
import operator
from math import factorial
def bcoef(n, k):
return factorial(n) / (factorial(k) * factorial(n - k))
def combinations(limit, start, used):
if limit == 0:
combs = (bcoef(4 if i != 10 else 16, x) for i, x in enumerate(used))
res = reduce(operator.mul, combs, 1)
return res
res = 0
for i in range(start, min(12, limit + 1)):
index = i if i != 11 else 1
available = 16 if index == 10 else 4
if used[index] < available:
used[index] += 1
res += combinations(limit - i, i, used)
used[index] -= 1
return res
print combinations(21, 1, [0] * 11) # 186184
所以我决定编写一个脚本，让每个可能的可行手牌都可以被检查。总数为 188052。由于我检查了所有可能的组合，因此这是确切的数字（而不是估计值）：
import itertools as it
big_list = []
def deck_set_up(m):
special = {8:'a23456789TJQK', 9:'a23456789', 10:'a2345678', 11:'a23'}
if m in special:
return [x+y for x,y in list(it.product(special[m], 'shdc'))]
else:
return [x+y for x,y in list(it.product('a23456789TJQKA', 'shdc'))]
deck_dict = {'as':1,'ah':1,'ad':1,'ac':1,
'2s':2,'2h':2,'2d':2,'2c':2,
'3s':3,'3h':3,'3d':3,'3c':3,
'4s':4,'4h':4,'4d':4,'4c':4,
'5s':5,'5h':5,'5d':5,'5c':5,
'6s':6,'6h':6,'6d':6,'6c':6,
'7s':7,'7h':7,'7d':7,'7c':7,
'8s':8,'8h':8,'8d':8,'8c':8,
'9s':9,'9h':9,'9d':9,'9c':9,
'Ts':10,'Th':10,'Td':10,'Tc':10,
'Js':10,'Jh':10,'Jd':10,'Jc':10,
'Qs':10,'Qh':10,'Qd':10,'Qc':10,
'Ks':10,'Kh':10,'Kd':10,'Kc':10,
'As':11,'Ah':11,'Ad':11,'Ac':11}
stop_here = {2:'As', 3:'8s', 4:'6s', 5:'4h', 6:'3c', 7:'3s', 8:'2h', 9:'2s', 10:'2s', 11:'2s'}
for n in range(2,12): # n is number of cards in the draw
combos = it.combinations(deck_set_up(n), n)
stop_point = stop_here[n]
while True:
try:
pick = combos.next()
except:
break
if pick[0] == stop_point:
break
if n < 8:
if len(set([item.upper() for item in pick])) != n:
continue
if sum([deck_dict[card] for card in pick]) == 21:
big_list.append(pick)
print n, len(big_list) # Total number hands that can equal 21 is 188052
在输出中，第一列是抽牌的张数，第二列是累计张数。因此，输出中“3”之后的数字是 2 张抽牌和 3 张抽牌的手牌总数，等于 21。小写字母 a 是低位 A（1 分），大写字母 A 是高位 A。我有一行（带有 set 命令的那一行），以确保它抛出任何有重复卡片的手。
该脚本需要 36 分钟才能 运行。因此，执行时间和准确性之间肯定存在权衡。 "big_list" 包含解决方案（即总和为 21 的每手牌）
>>>
================== RESTART: C:\Users\JBM\Desktop\bj3.py ==================
2 64
3 2100
4 14804
5 53296
6 111776
7 160132
8 182452
9 187616
10 188048
11 188052 # <-- This is the total count, as these numbers are cumulative
>>>