Kos - 1 year ago 48

Python Question

Some assumptions:

- One deck of 52 cards is used
- Picture cards count as 10
- Aces count as 1 or 11
- 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 Source

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