combination function in python

[Steven D'Aprano]

On Sun, 15 Apr 2007 02:38:31 -0700, bearophileHUGS wrote:

> DanielJohnson:
>> Please help, I couldnt find the function through help.
> 
> You can't find it because it's not there:
> 
> def factorial(n):
>     """factorial(n): return the factorial of the integer n.
>     factorial(0) = 1
>     factorial(n) with n<0 is -factorial(abs(n))
>     """
>     result = 1
>     for i in xrange(1, abs(n)+1):
>         result *= i
>     if n >= 0:
>         return result
>     else:
>         return -result
> 
> def binomial(n, k):
>     """binomial(n, k): return the binomial coefficient (n k)."""
>     assert n>0 and isinstance(n, (int, long)) and isinstance(k, (int,
> long))
>     if k < 0 or k > n:
>         return 0
>     if k == 0 or k == n:
>         return 1
>     return factorial(n) // (factorial(k) * factorial(n-k))


That's a naive and slow implementation. For even quite small values of n
and k, you end up generating some seriously big long ints, and then have
to (slowly!) divide them.

A better implementation would be something like this:

def binomial(n, k):
    if not 0 <= k <= n:
        return 0
    if k == 0 or k == n:
        return 1
    # calculate n!/k! as one product, avoiding factors that 
    # just get canceled
    P = k+1
    for i in xrange(k+2, n+1):
        P *= i
    # if you are paranoid:
    # C, rem = divmod(P, factorial(n-k))
    # assert rem == 0
    # return C
    return P//factorial(n-k)


There's probably even a really clever way to avoid that final division,
but I suspect that would cost more in time and memory than it would save.


-- 
Steven.