Some assumptions:
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?
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