If I roll four six-sided dice and add up the three highest, I will generate a number
from 3 to 18. There are 1296 (6^4) combinations possible. I want to calculate how
many combinations will add up to each of the possible totals.
By brute force methods I've determined that the distribution is as follows:
Result, # of combinations yielding that result
3 1
4 4
5 10
6 21
7 38
8 62
9 91
10 122
11 148
12 167
13 172
14 160
15 131
16 94
17 54
18 21
Although I can determine the distribution by brute force, I'm trying to find a method of
calculating a certain sum: like, a formula that would give 91 as solution to sum of 9.
Is it possible?
I can't think of a formula that's easier to calculate than brute force (any formula I could think of would involve considering a cumbersome number of cases), but I can offer a more efficient algorithm. The advantage will only really be felt if you are rolling more dice. Let n be the number dice rolled. Then brute force will be fast up to about n = 10, but beyond that this algorithm will be much better.
Now, I'm not sure which generalisation to higher n you'd be more interested in: the total of the highest 3 dice, or of the highest n-1 dice. So, I'll just explain the algorithm for finding the distribution of total value of all dice; it'll be easier to follow that way anyway.
I'll try to keep the syntax/notation general. We'll need an array/list notation of some sort; I'll use brackets, so if we have a list L, then the ith element will be denoted L[i]. Indexing starts at 0, not 1. So a list L of size 3 will have elements L[0], L[1], and L[2]. The size of the list will be denoted len(L).
Start out with a list L1 of size 1, and set L1[0] = 1.
This part will be performed n times: Create a new list L2 of size len(L1) + 6. All elements of L2 are initialised to 0. For all i from 0 to len(L1) - 1, and for all j from 1 to 6, increment L2[i+j] by L1[i]. Then set L1 = L2.
The final L1 will contain the distribution of all possible totals. These numbers get large very fast, so for certain programming languages, care should be taken regarding integer overflow.
I'd have to think how to modify the algorithm to only deal with certain dice rather than all dice, but I'm confident it could be done without too much trouble.
After a little thought:
The generalisation to highest n-1 dice is easy. Just make it a 2-dimensional list; we can think of the first index as rows and second index as columns, denoting the element at ith row and jth column as L[i][j] and denoting the size by rows(L) and cols(L). So in our variation, rows(L) will always be 7, containing the value of the lowest die, and cols(L) will increase by 6 each time as in the above description. Then the total of the highest n-1 dice is given by the column index minus the row index.
There may be more efficient ways to do that, but it's straightforward and still fast.
Then for highest 3 dice: using a 3-dimensional 7 x 7 x 7 list (whose size would not grow from one iteration to the next) would be straightforward, again maybe not the most efficient, but still fast.