473,696 Members | 1,759 Online
Bytes | Software Development & Data Engineering Community
+ Post

Home Posts Topics Members FAQ

combination function in python

how to use the combination function in python ?

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

Please help, I couldnt find the function through help.

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

Please help, I couldnt find the function through help.
If you download and install gmpy, it's easy:
>>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
want to download gmpy and don't care for gmpy's superb speed.
Alex

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

Bye,
bearophile

Apr 15 '07 #3
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.

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.

Similar topics

9
1708
by: Paul Rubin | last post by:
I'm trying the super() function as described in Python Cookbook, 1st ed, p. 172 (Recipe 5.4). class A(object): def f(self): print 'A' class B(object): def f(self):
1
3967
by: Bo Xu | last post by:
Object of Combination By Bo Xu Introduction A combination of n things, taken s at a time, often referred as an s-combination out of n, is a way to select a subset of size s from a given set of size n. There are n!/(s!(n-s)!) ways to do this. Donald E. Knuth gives several methods (algorithms) to generate all the s-combinations in . In such procedure-oriented way, each s-combination is processed while it's being generated. In some
3
6013
by: gdogg1587 | last post by:
Greetings. I'm working on a program that will "descramble" words. Think of a word scramble game where there is a list of characters, and several blank spaces to denote the word(s) that you are to come up with from the list. i.e.(* denotes a space): _ _ _ _ _ * _ _ _ _ _ _ characters: .hwodlelrlo answer: hello world.
4
2314
by: kivan.maharaj | last post by:
What I want to do is write a program to test lexicographical combinations of various sets of numbers to a predefined number and write that true values to a text file. Example: Number choosen between 1 and 50 Number set = 6
8
5632
by: Mir Nazim | last post by:
Hello, I need to write scripts in which I need to generate all posible unique combinations of an integer list. Lists are a minimum 12 elements in size with very large number of possible combination(12!) I hacked a few lines of code and tried a few things from Python CookBook (http://aspn.activestate.com/ASPN/Cookbook/), but they are hell slow.
2
5324
by: f rom | last post by:
----- Forwarded Message ---- From: Josiah Carlson <jcarlson@uci.edu> To: f rom <etaoinbe@yahoo.com>; wxpython-users@lists.wxwidgets.org Sent: Monday, December 4, 2006 10:03:28 PM Subject: Re: 1>make_buildinfo.obj : error LNK2019: unresolved external symbol __imp__RegQueryValueExA@24 referenced in function _make_buildinfo2 Ask on python-list@python.org . - Josiah
13
2590
by: Mohammad Omer | last post by:
Hi, I am working on SDI base application using vs2k5. I need to perform some task on combination of keys (link ctrl+v). I wrote WM_KEYDOWN message in my view for control command keys (like Delete, Insert, etc) but unable to catch combination of keys in WM_KEYDOWN message. I tried to use GetKeyStatus function in WM_KEYDOWN message but not gets any positive results. Please guide me, how I can control combination of keys in WM_KEYDOWN...
2
1378
by: dohertywa | last post by:
Hi: I'm working with probstat module which does an excellent job for the project I'm working on. I am passing the Combination objects I generate to generator functions that allow me to scale down the results. I am trying to find a way however to store the end resultant Combination object. Try to pickle it, and Python segfaults.
20
2986
by: sophia | last post by:
Dear all, The following is the program which i have done to find all the combination of letters in the string "hello" #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 5
0
8666
marktang
by: marktang | last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look ! Part I. Meaning of...
0
9010
jinu1996
by: jinu1996 | last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth. The Art of Business Website Design Your website is...
0
8853
tracyyun
by: tracyyun | last post by:
Dear forum friends, With the development of smart home technology, a variety of wireless communication protocols have appeared on the market, such as Zigbee, Z-Wave, Wi-Fi, Bluetooth, etc. Each protocol has its own unique characteristics and advantages, but as a user who is planning to build a smart home system, I am a bit confused by the choice of these technologies. I'm particularly interested in Zigbee because I've heard it does some...
0
7703
agi2029
by: agi2029 | last post by:
Let's talk about the concept of autonomous AI software engineers and no-code agents. These AIs are designed to manage the entire lifecycle of a software development project—planning, coding, testing, and deployment—without human intervention. Imagine an AI that can take a project description, break it down, write the code, debug it, and then launch it, all on its own.... Now, this would greatly impact the work of software developers. The idea...
0
5857
by: conductexam | last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one. At the time of converting from word file to html my equations which are in the word document file was convert into image. Globals.ThisAddIn.Application.ActiveDocument.Select();...
0
4356
by: TSSRALBI | last post by:
Hello I'm a network technician in training and I need your help. I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs. The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols. I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
0
4611
by: adsilva | last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
2
2319
muto222
by: muto222 | last post by:
How can i add a mobile payment intergratation into php mysql website.
3
1992
bsmnconsultancy
by: bsmnconsultancy | last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.