combination function in python

[Anton Vredegoor]

Jussi Piitulainen wrote:

>> 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.

We're getting closer and closer to something I already posted a few 
times here. This implementation was unfortunate because I consistently 
used an uncommon name for it so people couldn't easily find it (mea 
culpa), and maybe also because it uses the despised reduce builtin.

def noverk(n,k):
     return reduce(lambda a,b: a*(n-b)/(b+1),xrange(k),1)

BTW I hereby give up the strange name for this and request a better name 
that everybody will use so there will be no confusion anymore. Maybe 
comb(n,k) ?

> Here's one non-clever one for integers n, k that uses n^k / k^k
> (falling powers) with the smaller of k and n - k as lower index:
> 
> 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


Ha, my function uses smaller subproducts :-)

A.