473,696 Members | 1,759 Online

# combination function in python

how to use the combination function in python ?

For example 9 choose 2 (written as 9C2) = 9!/7!*2!=36

Apr 15 '07 #1
17 8090
DanielJohnson <di********@gma il.comwrote:
how to use the combination function in python ?

For example 9 choose 2 (written as 9C2) = 9!/7!*2!=36

>>import gmpy
gmpy.comb(9,2 )
mpz(36)

However, there's no equivalent function built into Python, if that's
what you're asking (gmpy's a third-party extension). It's of course
easy to write one for yourself, if you want the functionality but don't
Alex

Apr 15 '07 #2
DanielJohnson:
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))

Bye,
bearophile

Apr 15 '07 #3
On Sun, 15 Apr 2007 02:38:31 -0700, bearophileHUGS wrote:
DanielJohnson:

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.

Apr 15 '07 #4
Steven D'Aprano:
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:
You are right, thank you for the improvement (the advantage of the
older implementation is that it's naive, so it's a bit more probably
correct compared to more complex code I may write. For Python code I
often tend to write a naive version first, create many testcases,
slowly fixing all the corner cases (like factorial(-5)), and only
later find a faster/better implementation if I have some time to do it
or if I need it. If I need to do lot of binomials the gmpy by Alex
helps).

Bye,
bearophile

Apr 15 '07 #5
Steven D'Aprano writes:
bearophileHUGS wrote:
....
> 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 _definition_ of the binomial coefficient with upper index r
and lower index k is (r * (r - 1) * ...) / (k * (k - 1) * ...) with k
factors in both products. These are called falling factorial powers by
Graham, Knuth and Patashnik. Their notation is to write n^k and k^k
but with the exponent underlined; the latter is just k!, when k 0. A
straightforward implementation below.
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.
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
Apr 15 '07 #6
On Apr 15, 8:37 am, Jussi Piitulainen <jpiit...@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

Apr 15 '07 #7
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.
Apr 15 '07 #8
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
Apr 15 '07 #9
Mark Dickinson:
def choose(n, k):
ntok = 1
for t in xrange(min(k, n-k)):
ntok = ntok*(n-t)//(t+1)
return ntok
With few tests, it seems this is faster than the version by Jussi only
with quite big n,k.

(Another test to be added, is the assert n>0 of my original version
(testing that n,k seem useful too)).

Bye,
bearophile

Apr 15 '07 #10

This thread has been closed and replies have been disabled. Please start a new discussion.