Kos Kos - 3 months ago 12
Python Question

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

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

Here's another way of doing it which doesn't track the different combinations but just returns the number of them:

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, 12):
        if i > limit:
            break

        # Aces are at index 1 no matter if value 11 or 1 is used
        index = i if i != 11 else 1

        # This should be 16 for used[10] but it doesn't matter since
        # it's well above limit of 21
        if used[index] < 4:
            used[index] += 1
            res += combinations(limit - i, i, used)
            used[index] -= 1

    return res

print combinations(21, 1, [0] * 11) # 416

Above considers only the face value of the card so Ten, Jack, Queen and King are the same. It doesn't consider suits either. It can be extended to include suits and differentiate between cards with value of 10 by calculating how many different ways there are to pick n cards with same face value:

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:
        # For each face value figure out how many combinations can be used
        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, 12):
        if i > limit:
            break

        index = i if i != 11 else 1

        if used[index] < 4:
            used[index] += 1
            res += combinations(limit - i, i, used)
            used[index] -= 1

    return res

print combinations(21, 1, [0] * 11) # 186184