python中的组合函数 [英] combination function in python
问题描述
如何在python中使用组合功能？
例如9选择2（写成9C2）= 9！/ 7！* 2！= 36
请帮助，我无法通过帮助找到该功能。
DanielJohnson< di *** *****@gmail.com写道：
如何在python中使用组合函数？
例如9选择2（写成9C2）= 9！/ 7！* 2！= 36
请帮助，我无法通过帮助找到该功能。
如果您下载并安装gmpy，它很容易：
< blockquote class =post_quotes>
>> import gmpy
gmpy.comb（9,2）
mpz（36）
然而，Python中没有内置的等效函数，如果那是'
你是什么问（gmpy'的第三方扩展）。它当然是
很容易为自己写一个，如果你想要的功能但不要
想要下载gmpy并且不在乎gmpy'极好的速度。
Alex
DanielJohnson：
请帮助，我无法通过帮助找到该功能。
你找不到它，因为它不存在：
def factorial（n）：
""" factorial（n）：返回整数n的阶乘。
阶乘（0）= 1
阶乘（ n）n< 0 is -factorial（abs（n））
"""
result = 1
for i in xrange（1，abs（n）+1）：
result * = i
如果n> = 0：
返回结果
else：
return -result
def二项式（n，k）：
" ;""二项式（n，k）：返回二项式系数（nk）。""
断言n> 0和isinstance（n，（int，long））和isinstance（k，（int，
long））
如果k< 0或kn：
返回0
如果k == 0或k == n：
返回1
返回阶乘（n）//（阶乘（k）*阶乘（nk））
再见，
熊宝宝
On Sun，2007年4月15日02:38:31 -0700，bearophileHUGS写道：
DanielJohnson：
>请帮助，我无法通过帮助找到该功能。
你找不到它，因为它不存在：
def factorial（n）：
""" factorial（n）：返回整数n的阶乘。
阶乘（0）= 1
阶乘（ n）n< 0 is -factorial（abs（n））
"""
result = 1
for i in xrange（1，abs（n）+1）：
result * = i
如果n> = 0：
返回结果
else：
return -result
def二项式（n，k）：
" ;""二项式（n，k）：返回二项式系数（nk）。""
断言n> 0和isinstance（n，（int，long））和isinstance（k，（int，
long））
如果k< 0或kn：
返回0
如果k == 0或k == n：
返回1
return factorial（n）//（factorial（k）* factorial（nk））
这是一个天真而缓慢的实现。对于非常小的n $ / b $ b和k值，你最终会产生一些非常大的长整数，然后将（b = b）b（慢慢地）除以它们。
一个更好的实现是这样的：
def二项式（n，k）：
如果不是0< ; = k< = n：
返回0
如果k == 0或k == n：
返回1
＃计算n！/ k！作为一种产品，避免因为
＃刚被取消的因素
P = k + 1
$ x $ b for x in xrange（k + 2，n +1）：
P * = i
＃如果你是偏执狂：
＃C，rem = divmod（P，factorial（nk） ））
＃assert rem == 0
＃return C
返回P // factorial（nk）
甚至可能有一种非常聪明的方法来避免最终的分裂，
但是我怀疑它会花费更多的时间和内存而不是它能节省的费用。
- -
史蒂文。
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.
DanielJohnson <di********@gmail.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
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
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.
这篇关于python中的组合函数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
