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. 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 thirdparty 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
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(nk))
Bye,
bearophile
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(nk))
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(nk))
# assert rem == 0
# return C
return P//factorial(nk)
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.
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
Steven D'Aprano writes:
bearophileHUGS wrote:
....
> return factorial(n) // (factorial(k) * factorial(nk))
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(nk))
# assert rem == 0
# return C
return P//factorial(nk)
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 nonclever 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
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, nk)):
ntok = ntok*(nt)//(t+1)
return ntok
Mark
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*(nb)/(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 nonclever 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.
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, nk)):
ntok = ntok*(nt)//(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
Mark Dickinson:
def choose(n, k):
ntok = 1
for t in xrange(min(k, nk)):
ntok = ntok*(nt)//(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 This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics 
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):

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
scombination out of n, is a way to select a subset of size s from a
given set of size n. There are n!/(s!(ns)!) ways to do this. Donald
E. Knuth gives several methods (algorithms) to generate all the
scombinations in . In such procedureoriented way, each
scombination is processed while it's being generated. In some

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.

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

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.
 
by: f rom 
last post by:
 Forwarded Message 
From: Josiah Carlson <jcarlson@uci.edu>
To: f rom <etaoinbe@yahoo.com>; wxpythonusers@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 pythonlist@python.org .
 Josiah

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

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.

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

by: marktang 
last post by:
ONU (Optical Network Unit) is one of the key components for providing highspeed 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...

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...
 
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, ZWave, WiFi, 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...

by: agi2029 
last post by:
Let's talk about the concept of autonomous AI software engineers and nocode 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...

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();...

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 LANtoLAN VPNs.
The last exercise I practiced was to create a LANtoLAN 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...

by: adsilva 
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?

by: muto222 
last post by:
How can i add a mobile payment intergratation into php mysql website.
 
by: bsmnconsultancy 
last post by:
In today's digital era, a welldesigned 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...
 