June 25, 2007, at 08:33 AM
Tips /

FactorialInPython

Found that out trying to compute a probability (boy it has been a long time) using Python.

import operator

def fac(n):
    return reduce(operator.mul,range(2,n+1),1)

Must remember to try to understand how it works, and the Birthday Paradox while I am at it :P This explanation seems simpler / clearer.

As per the Pyhton documentation of the reduce function:

reduce(function, sequence[, initializer])

Apply function of two arguments cumulatively to the items of sequence, from left to right, so as to reduce the sequence to a single value. For example, reduce(lambda x, y: x+y, [1, 2, 3, 4, 5]) calculates ((((1+2)+3)+4)+5). The left argument, x, is the accumulated value and the right argument, y, is the update value from the sequence. If the optional initializer is present, it is placed before the items of the sequence in the calculation, and serves as a default when the sequence is empty. If initializer is not given and sequence contains only one item, the first item is returned.

Roberto De Almeida wrote me an email stating that the operator.mul could be replaced by a lamba function as in:

def fac(n):
    return reduce(lambda x, y: x * y,range(2,n+1),1)

I get the Python part and believe I understood (or should I say remembered I understood) the Birthday Paradox.

I wanted to compute a generalized version i.e. the probability p(n,d) that at least two integers are the same in a given set of n random integers drawn from a discrete uniform distribution range [1,d]. The approximation did the job nicely!

I can't miss that opportunity to show off my mimeTex.

p(n,d) \approx 1-exp(-\frac{n(n-1)}{2d})