combination function in python

[Mark Dickinson]

On Apr 15, 8:37 am, Jussi Piitulainen <jpiit... at ling.helsinki.fi>
wrote:
> def choose(n, k):
>    if 0 <= k <= n:
>        ntok = 1
>        ktok = 1
>        for t in xrange(1, min(k, n - k) + 1):
>           ntok *= n
>           ktok *= t
>           n -= 1
>        return ntok // ktok
>    else:
>        return 0

It might be even better to do the divisions as you go, rather than
leaving
them all to the end.  That way the intermediate results stay smaller.
So
(leaving out the bounds checking) one just does:

def choose(n, k):
    ntok = 1
    for t in xrange(min(k, n-k)):
        ntok = ntok*(n-t)//(t+1)
    return ntok

Mark