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