如何找到21点的方法数？

Question

一些假设：

1. 使用一副52张牌
2. 图片卡数为10
3. A数为1或11
4. 顺序并不重要（即王牌+皇后与皇后+王牌相同）

我想我会按顺序尝试所有可能的组合，看看哪一个加起来是21，但是有太多的方法来混合卡片（52！方法）。这种方法也没有考虑到顺序不重要，也没有考虑到任何一张牌最多只能有4种类型（黑桃、梅花、钻石、红桃）。在

现在我想的问题是：

我们有11个“插槽”。每一个插槽里都有53个可能的东西：52张卡中的1张或者根本没有卡。之所以设11个槽，是因为11张牌是最多可以发的牌数，加起来还是21张；11张以上的牌加起来要超过21张。在

然后“最左边”的插槽将递增一个，并检查所有11个插槽，看它们是否加起来为21（0表示插槽中没有卡）。否则，右边的下一个插槽将递增，下一个插槽，依此类推。在

一旦前4个插槽包含相同的“卡”（在四个增量之后，前4个插槽都将是1），第五个插槽就不可能是这个数字，因为有4个任何类型的数字。然后，第五个插槽将成为剩余可用卡中的下一个最低编号；在四个1的情况下，第五个插槽将变成2，以此类推。在

你会怎么做？在

Answer 1

在担心花色和不同的价值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

由于我们关注的是不同的卡片组合而不是不同的价值组合，因此应该修改上面的基本情况，以返回可用于生成价值组合的不同卡片组合的数量。幸运的是，这是一个非常简单的任务，Binomial coefficient可以用来计算从n项中选择多少个不同的k项组合。在

一旦知道used中每个值的不同卡片组合的数量，它们就可以相互相乘以获得最终结果。例如5, 5, 10, 1值5结果为bcoef(4, 2) == 6，值{}到{}，值{}到{}。对于所有其他值bcoef(x, 0)结果为1。将这些值相乘得到6 * 16 * 4 == 384，然后返回：

^{2}$

Answer 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

按以下步骤设置您的卡

^{2}$

那就打电话给你的部门

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和击球）

Answer 3

所以我决定写一个脚本来检查每一个可能的手。总数是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表示低ace（1分），大写字母a表示高位ace。我有一个行（使用set命令的那一行），以确保它抛出任何有重复卡的手。在

脚本运行需要36分钟。所以在执行时间和准确性之间肯定有一个权衡。“大名单”包含解决方案（即每只手的总和为21）

^{2}$