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
--
http://mail.python.org/mailman/listinfo/python-list
