combination function in python

[Jussi Piitulainen]

Mark Dickinson writes:
> Jussi Piitulainen 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

Yes, that's what I once saw done. Thanks. Its correctness is more
subtle, so I prefer to add the parentheses below to emphasise that
the product has to be computed before the division. I also renamed
the variable to p: it's no longer n^k (falling). And I put the
bounds back in.

def choose(n, k):
    if 0 <= k <= n:
        p = 1
        for t in xrange(min(k, n - k)):
            p = (p * (n - t)) // (t + 1)
        return p
    else:
        return 0