probability of T total eyes when throwing N dice with S sides
Question: I want to calculate the probability of the event that the sum of all eyes of
`n` dice with `s` sides (numbered from 1 to `s`) is equal to `t`. My language
is Python 3.

My current approach is pretty much a try-and-count solution and only works for
small numbers (running `probability(10, 10, 50)` already ate all my RAM and
forced me to hard reset):

    
    
    import itertools
    def probability(n, s, t):
        all_rolls=list(itertools.product(range(1,s+1), repeat=n))
        target_rolls=[l for l in all_rolls if sum(l)==t]
        return round(len(target_rolls)/len(all_rolls), 4)
    

But I honestly don't know how else to solve this. Can you please help me to
get on the right track?


Answer: first off: the total possible roll combinations will always be `s**n`, so you
don't need to store a list of all possibilities in order to get it's length.
Similarly you can just keep a running total of desired outcomes instead of
keeping a list of them to save on memory space but it still won't speed up the
function a whole lot:

    
    
    def probability(n, s, t):
        all_rolls = itertools.product(range(1,s+1), repeat=n) #no list, leave it a generator
        target_rolls=sum(1 for l in all_rolls if sum(l)==t) #just total them up
        return round(target_rolls/s**n, 4)
    

A much more efficient way of calculating the possibilities is with a `dict`
and some clever iteration. Each dictionary will use the roll value as keys and
frequency as value, each iteration the `prev` will be this dict for the
previous X dice and `cur` will be updated from it with the addition of another
die:

    
    
    import collections
    def probability(n, s, t):
        prev = {0:1} #previous roll is 0 for first time
        for _ in range(n):
            cur = collections.defaultdict(int) #current probability
            for r,times in prev.items():
                for i in range(1,s+1):
                    #if r occured `times` times in the last iteration then
                    #r+i have `times` more possibilities for the current iteration.
                    cur[r+i]+=times
            prev = cur #use this for the next iteration
    
        return cur[t] / s**n
        #return round(cur[t] / s**n , 4)
    

note 1: since `cur` is a defaultdict trying to look up a number that is not
not possible with the given input will return 0

note 2: since this method puts together a dictionary with all possible
outcomes you can return `cur` and do the calculation for multiple different
possible outcomes on the same dice rolls.

