I’m playing a game which has eight slots for 32 abilities. Any or all slots can be empty.
There are four pairs of mutually exclusive abilities (ie they cannot both be selected at the same time), and one trio of mutually exclusive abilities (only one of the three can be included). These two categories do not overlap with each other in any way.
So the game stores high scores for each possible combination of abilities. Wow, I thought, I wonder how many different scores the game needs to keep track of.
I just want to be sure I’m understanding the scoring system correctly. If a pair of abilities are connected, you can only have one slot filled in the pair? If so, then you can essentially treat it as a single ability with sixteen slots. Same thing with the three connected abilities. And because each ability can be empty, you should treat them as if they have an additional slots of zero.
So if my math is correct you have 9 to 21 x 17 to 4 x 25. The answer is approximately 228,469,584,781,326,100,000,000,000.
There are 4 pairs of abilities such that, from each, you may choose to take either none or one of their 2 abilities.
There is a triple of abilities from which you may choose to take either none or one of its 3 abilities.
There are 21 remaining abilities, each of which you may choose to not take or take.
Overall, you may choose to take anywhere from 0 through 4 abilities.
All that matters is which abilities you choose to take and which you choose not to take (there is no concept of order or repetition). You wish to know in how many ways these choices can be made.
In that case, what you seek is the sum of the 0th through 4th degree coefficients of the polynomial (1 + 2x)[sup]4[/sup](1 + 3x)(1 + x)[sup]21[/sup]. This is 1 + 32 + 489 + 4752 + 32991 = 38265.
Overall, you may choose to take anywhere from 0 through 8 abilities.
Thus, what you seek is the sum of the 0th through 8th degree coefficients of said polynomial. This is 1 + 32 + 489 + 4,752 + 32,991 + 174,264 + 728,231 + 2,471,416 + 6,937,698 = 10,349,874.
You’ve given an answer much larger than 2[sup]32[/sup] (which is approximately 4 billion). Thus, you must be interpreting the question as something other than counting particular subsets of the 32 abilities.
Here’s another way to get the same answer as Indistinguishable. (He may have used a manipulater like Wolfram; the following may be easier if all you have is bc.) Rephrasing the problem: You want the number of distinct ways to select up to eight items (unordered) from a set of 32. The 32 items include a trio, 4 pairs and 21 singletons.
Now we need to do the calculations! In the following, everything indented is input to a ‘bc’ calculater.
We’ll need the combination counting function combo(x, y)
The number of solutions with just a singletons is combo(21,a)
The number of solutions with just b pairs is q**:
q[0] = 1; q[1] = 8; q[2] = 24; q[3] = 32; q[4] = 16
The number of solutions with just d items from the trio is r[d]:
r[0] = 1; r[1] = 3
So let’s loop over the possibilities
numsol = 0;
for (tot = 0; tot <= 8; tot++) {
[INDENT] ns = 0;
for (a = 0; a <= tot; a++)
for (b = 0; a+b <= tot && b <= 4; b++) {
[INDENT] d = tot-a-b;
if (d == 0 || d == 1)
[INDENT] ns += combo(21,a) * q** * r[d];[/INDENT]
}
print "Solutions with ", tot, " items number ", ns, "
"
numsol += ns;[/INDENT]
}
print "Grand total = ", numsol, "
"[/INDENT]
When I run this I get
Solutions with 0 items number 1
Solutions with 1 items number 32
Solutions with 2 items number 489
Solutions with 3 items number 4752
…
Grand total = 10349874
(More specifically, what Little Nemo counted is this: number of ways to assign some (possibly none, possibly all) of the abilities to slots in a manner satisfying the noted exclusion conditions (that is, not taking more than one ability from any of the 4 pairs or the trio), but allowing a slot to take on multiple abilities (as well as none or one), and distinguishing in the count between different orderings of the slots.)
And just to clarify: what septimus’s code is doing is precisely the polynomial multiplication I noted, with q as the coefficients of the polynomial (1 + 2x)[sup]4[/sup], with r as the coefficients of the polynomial (1 + 3x), and with combo(21, a) as the a-th degree coefficient of the polynomial (1 + x)[sup]21[/sup].
(Note that it’s actually faster to compute the binomial coefficients [that is, the outputs of the function “combo”] via “repeated squaring” of (1 + x) than via computation and division of large factorials as prescribed in the provided code (thus, we may compute (1 + x)[sup]21[/sup] as (1 + x) * (1 + x)[sup]4[/sup] * (1 + x)[sup]16[/sup], where each factor happens to be the squared square of the previous one). Note also that as we are only ultimately interested in terms up through degree 8, we can drop any higher degree terms from consideration immediately once they arise.)
(Incidentally, I did use Wolfram Alpha for the calculation before, because, why not? But if one wants some code from (relative, always relative) scratch to run to the same effect, here is some Haskell:
degree = 8 -- Maximum degree of terms we are interested in
-- We have two convenient representations of polynomials:
-- A) Lists of coefficients
-- B) Functions from degrees to corresponding coefficients
-- We define utility functions to readily convert between these:
listToFunc list index = (list ++ (repeat 0)) !! index
funcToList func = map func [0..degree]
funcOpToListOp op p q = funcToList (op (listToFunc p) (listToFunc q))
-- Arithmetic operations on polynomials:
mult = funcOpToListOp mult'
where mult' p q deg = sum [(p i) * (q (deg - i)) | i <- [0..deg]]
square p = mult p p
power p 0 = [1]
power p 1 = p
power p n = mult (square (power p d)) (power p m) where (d, m) = divMod n 2
-- The answers we are interested in:
answerPoly = mult (mult (power [1, 2] 4) [1, 3]) (power [1, 1] 21)
answer = sum answerPoly
This results in answerPoly = [1,32,489,4752,32991,174264,728231,2471416,6937698] and answer = 10349874, as before.)
Well, I suppose this depends on how slow you take division to be. If you consider division to be a fast primitive operation, then you may want to take a factorial-esque approach, but removing much of the redundant calculation: specifically, letting f(n, k, i) be the i-th degree coefficient of (1 + kx)[sup]n[/sup], we may enumerate these for fixed n and k using the recursion f(n, k, i + 1) = f(n, k, i) * k * (n - i) / (i + 1), with the base case f(n, k, 0) = 1. [combo(x, y) is the special case f(x, 1, y)].
Thanks, guys! Yes, the assumptions in post 4 are correct.
When I saw how big the number was, I started wondering how the game stored all those stats, but then I realized no one sane would do every possible combination. Wonder how many it does store…
Presumably, it stores the high scores in a file of variable length, and only adds an entry for a particular choice of abilities the first time you play that choice. So if you play a dozen different combinations, the file will have a dozen lines in it.
Wonder how many it does store…