Dice probability problem

[Alexander Schmolck]

Tomi Lindberg <tomi.lindberg.NO_SPAM at pp.inet.fi.invalid> writes:

> I'm trying to find a way to calculate a distribution of outcomes with any
> combination of dice. I have the basics done, but I'm a bit unsure how to
> continue. My main concern is how to make this accept any number of dice,
> without having to write a new list comprehension for each case?

You need to think about the right way to break the problem down into some
operation that can be repeated one fewer times than there are dice (if you
just have a single dice, nothing needs to be done) and then repeat it.

An obvious candidate is adding a single dice to the sums computed so far:

    def addDice(sums, dice):
        return [x+y for x in dice for y in sums]

If you have less than 1 dice the answer is 
    # len(pool) == 1
    pool[0]

After that, each time you add a dice you need to call addDice on the sum
computed for all the previous dice and the new dice:

    # len(pool) == 2
    addDice(resultFor1, pool[1])
    addDice(pool[0], pool[1])

then

    # len(pool) == 3
    addDice(resultFor2, pool[2])
    addDice(addDice(resultFor1, pool[1]), pool[2])
    addDice(addDice(pool[0], pool[1]), pool[2])

finally you get

    # len(pool) == n
    addDice(addDice(addDice(..., pool[n-3]), pool[n-2]) pool[n-1])

OK, so how do we get the repetition?

Conveniently the pattern f(...f(f(x[0],x[1]),x[2])...,x[n-1]) or equivalently,
if we write the infix operator * for f: x[0]*x[1]*...*x[n-1], can just be written as
reduce(f, x) in python. So we get:

reduce(addDice, pool)
== reduce(lambda sums, dice: [x+y for x in dice for y in sums], pool)

You should presumably also try writing this out as a single function, without
using reduce (but recognizing the (left) reduction pattern is useful, even if
you don't use python's reduce).

'as