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 1

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.