How to find the number of ways to get 21 in Blackjack?

Question

Some assumptions:

1. One deck of 52 cards is used
2. Picture cards count as 10
3. Aces count as 1 or 11
4. The order is not important (ie. Ace + Queen is the same as Queen + Ace)

I thought I would then just sequentially try all the possible combinations and see which ones add up to 21, but there are way too many ways to mix the cards (52! ways). This approach also does not take into account that order is not important nor does it account for the fact that there are only 4 maximum types of any one card (Spade, Club, Diamond, Heart).

Now I am thinking of the problem like this:

We have 11 "slots". Each of these slots can have 53 possible things inside them: 1 of 52 cards or no card at all. The reason it is 11 slots is because 11 cards is the maximum amount of cards that can be dealt and still add up to 21; more than 11 cards would have to add up to more than 21.

Then the "leftmost" slot would be incremented up by one and all 11 slots would be checked to see if they add up to 21 (0 would represent no card in the slot). If not, the next slot to the right would be incremented, and the next, and so on.

Once the first 4 slots contain the same "card" (after four increments, the first 4 slots would all be 1), the fifth slot could not be that number as well since there are 4 numbers of any type. The fifth slot would then become the next lowest number in the remaining available cards; in the case of four 1s, the fifth slot would become a 2 and so on.

How would you do approach this?

Answer 1

divide and conquer by leveraging the knowledge that if you have 13 and pick a 10 you only have to pick cards to sum to 3 left to look at ... be forwarned this solution might be slow(took about 180 seconds on my box... it is definately non-optimal) ..

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

set up your cards as follows

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

then just call your function

for combination in sum_to(21,deck):
    print combination

unfortunately this does allow some duplicates to sneak in ... in order to get unique entries you need to change it a little bit

in sum_to on the last line change it to

  # sort our solutions so we can later eliminate duplicates
  yield sorted([i] + result) # append each further combination to our solutions

then when you get your combinations you gotta do some deep dark voodoo style python

 unique_combinations = sorted(set(map(tuple,sum_to(21,deck))),key=len,reverse=0)

 for combo in unique_combinations: print combo

from this cool question i have learned the following (keep in mind in real play you would have the dealer and other players also removing from the same deck)

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 !!!

keep in mind these are often suboptimal plays (ie considering A,10 -> 1,10 and hitting )

Answer 2

Before worrying about the suits and different cards with value 10 lets figure out how many different value combinations resulting to 21 there are. For example 5, 5, 10, 1 is one such combination. The following function takes in limit which is the target value, start which indicates the lowest value that can be picked and used which is the list of picked values:

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

Since we're interested about different card combinations instead of different value combinations the base case in above should be modified to return number of different card combinations that can be used to generate a value combination. Luckily that's quite easy task, Binomial coefficient can be used to figure out how many different combinations of k items can be picked from n items.

Once the number of different card combinations for each value in used is known they can be just multiplied with each other for the final result. So for the example of 5, 5, 10, 1 value 5 results to bcoef(4, 2) == 6, value 10 to bcoef(16, 1) == 16 and value 1 to bcoef(4, 1) == 4. For all the other values bcoef(x, 0) results to 1. Multiplying those values results to 6 * 16 * 4 == 384 which is then 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

Answer 3

So I decided to write the script that every possible viable hand can be checked. The total number comes out to be 188052. Since I checked every possible combination, this is the exact number (as opposed to an estimate):

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

In the output, the the first column is the number of cards in the draw, and the second number is the cumulative count. So the number after "3" in the output is the total count of hands that equal 21 for a 2-card draw, and a 3-card draw. The lower case a is a low ace (1 point), and uppercase A is high ace. I have a line (the one with the set command), to make sure it throws out any hand that has a duplicate card.

The script takes 36 minutes to run. So there is definitely a trade-off between execution time, and accuracy. The "big_list" contains the solutions (i.e. every hand where the sum is 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
>>>