Python 二项式系数
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/26560726/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Python Binomial Coefficient
提问by user3396351
import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == 1 or y == x:
print(1)
if y > x:
print(0)
else:
a = math.factorial(x)
b = math.factorial(y)
div = a // (b*(x-y))
print(div)
This binomial coefficient program works but when I input two of the same number which is supposed to equal to 1 or when y is greater than x it is supposed to equal to 0.
这个二项式系数程序有效，但是当我输入两个相同的数字时，应该等于 1，或者当 y 大于 x 时，它应该等于 0。
采纳答案by Shaun Coutts
This question is old but as it comes up high on search results I will point out that scipyhas two functions for computing the binomial coefficients:
这个问题很老，但当它出现在搜索结果中时，我会指出它scipy有两个用于计算二项式系数的函数：
scipy.special.binom()import scipy.special # the two give the same results scipy.special.binom(10, 5) # 252.0 scipy.special.comb(10, 5) # 252.0 scipy.special.binom(300, 150) # 9.375970277281882e+88 scipy.special.comb(300, 150) # 9.375970277281882e+88 # ...but with `exact == True` scipy.special.comb(10, 5, exact=True) # 252 scipy.special.comb(300, 150, exact=True) # 393759702772827452793193754439064084879232655700081358920472352712975170021839591675861424
scipy.special.binom()import scipy.special # the two give the same results scipy.special.binom(10, 5) # 252.0 scipy.special.comb(10, 5) # 252.0 scipy.special.binom(300, 150) # 9.375970277281882e+88 scipy.special.comb(300, 150) # 9.375970277281882e+88 # ...but with `exact == True` scipy.special.comb(10, 5, exact=True) # 252 scipy.special.comb(300, 150, exact=True) # 393759702772827452793193754439064084879232655700081358920472352712975170021839591675861424
Note that scipy.special.comb(exact=True)uses Python integers, and therefore it can handle arbitrarily large results!
请注意，scipy.special.comb(exact=True)使用 Python 整数，因此它可以处理任意大的结果！
Speed-wise, the three versions give somewhat different results:
速度方面，三个版本给出的结果有些不同：
num = 300
%timeit [[scipy.special.binom(n, k) for k in range(n + 1)] for n in range(num)]
# 52.9 ms ± 107 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
%timeit [[scipy.special.comb(n, k) for k in range(n + 1)] for n in range(num)]
# 183 ms ± 814 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)each)
%timeit [[scipy.special.comb(n, k, exact=True) for k in range(n + 1)] for n in range(num)]
# 180 ms ± 649 μs per loop (mean ± std. dev. of 7 runs, 10 loops each)
(and for n = 300, the binomial coefficients are too large to be represented correctly using float64numbers, as shown above).
（对于n = 300，二项式系数太大而无法使用float64数字正确表示，如上所示）。
回答by Tim Pietzcker
Your program will continue with the second ifstatement in the case of y == x, causing a ZeroDivisionError. You need to make the statements mutually exclusive; the way to do that is to use elif("else if") instead of if:
if在 的情况下y == x，您的程序将继续执行第二条语句，导致ZeroDivisionError. 你需要让这些陈述相互排斥；这样做的方法是使用elif("else if") 而不是if：
import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == x:
print(1)
elif y == 1: # see georg's comment
print(x)
elif y > x: # will be executed only if y != 1 and y != x
print(0)
else: # will be executed only if y != 1 and y != x and x <= y
a = math.factorial(x)
b = math.factorial(y)
c = math.factorial(x-y) # that appears to be useful to get the correct result
div = a // (b * c)
print(div)
回答by PM 2Ring
Here's a version that actually uses the correct formula. :)
这是一个实际使用正确公式的版本。:)
#! /usr/bin/env python
''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''
from math import factorial as fac
def binomial(x, y):
try:
binom = fac(x) // fac(y) // fac(x - y)
except ValueError:
binom = 0
return binom
#Print Pascal's triangle to test binomial()
def pascal(m):
for x in range(m + 1):
print([binomial(x, y) for y in range(x + 1)])
def main():
#input = raw_input
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
print(binomial(x, y))
if __name__ == '__main__':
#pascal(8)
main()
...
...
Here's an alternate version of binomial()I wrote several years ago that doesn't use math.factorial(), which didn't exist in old versions of Python. However, it returns 1 if r is not in range(0, n+1).
这是binomial()我几年前写的一个替代版本，它不使用math.factorial()，旧版本的 Python 中不存在。但是，如果 r 不在范围 (0, n+1) 内，则返回 1。
def binomial(n, r):
''' Binomial coefficient, nCr, aka the "choose" function
n! / (r! * (n - r)!)
'''
p = 1
for i in range(1, min(r, n - r) + 1):
p *= n
p //= i
n -= 1
return p
回答by firegurafiku
What about this one? :) It uses correct formula, avoids math.factorialand takes less multiplication operations:
这个如何？:) 它使用正确的公式，避免math.factorial并减少乘法运算：
import math
import operator
product = lambda m,n: reduce(operator.mul, xrange(m, n+1), 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(y+1, x) / product(1, x-y)
Also, in order to avoid big-integer arithmetics you may use floating point numbers, convert
product(a[i])/product(b[i])to product(a[i]/b[i])and rewrite the above program as:
此外，为了避免您可以使用浮点数，转换大整数算术
product(a[i])/product(b[i])来product(a[i]/b[i])和改写上述程序为：
import math
import operator
product = lambda iterable: reduce(operator.mul, iterable, 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(map(operator.truediv, xrange(y+1, x+1), xrange(1, x-y+1)))
回答by merrais
Here is a function that recursively calculates the binomial coefficients using conditional expressions
这是一个使用条件表达式递归计算二项式系数的函数
def binomial(n,k):
return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1))
回答by Slava
For Python 3, scipy has the function scipy.special.comb, which may produce floating point as well as exact integer results
对于 Python 3，scipy 具有函数 scipy.special.comb，它可能会产生浮点数以及精确的整数结果
import scipy.special
res = scipy.special.comb(x, y, exact=True)
See the documentation for scipy.special.comb.
请参阅scipy.special.comb的文档。
For Python 2, the function is located in scipy.misc, and it works the same way:
对于 Python 2，该函数位于 scipy.misc 中，其工作方式相同：
import scipy.misc
res = scipy.misc.comb(x, y, exact=True)
回答by alisianoi
So, this question comes up first if you search for "Implement binomial coefficients in Python". Only this answerin its second part contains an efficient implementation which relies on the multiplicative formula. This formula performs the bare minimum number of multiplications. The function below does not depend on any built-ins or imports:
因此，如果您搜索“在 Python 中实现二项式系数”，首先会出现这个问题。只有第二部分中的这个答案包含依赖于乘法公式的有效实现。该公式执行最少数量的乘法。下面的函数不依赖于任何内置或导入：
def fcomb0(n, k):
'''
Compute the number of ways to choose $k$ elements out of a pile of $n.$
Use an iterative approach with the multiplicative formula:
$$\frac{n!}{k!(n - k)!} =
\frac{n(n - 1)\dots(n - k + 1)}{k(k-1)\dots(1)} =
\prod_{i = 1}^{k}\frac{n + 1 - i}{i}$$
Also rely on the symmetry: $C_n^k = C_n^{n - k},$ so the product can
be calculated up to $\min(k, n - k).$
:param n: the size of the pile of elements
:param k: the number of elements to take from the pile
:return: the number of ways to choose k elements out of a pile of n
'''
# When k out of sensible range, should probably throw an exception.
# For compatibility with scipy.special.{comb, binom} returns 0 instead.
if k < 0 or k > n:
return 0
if k == 0 or k == n:
return 1
total_ways = 1
for i in range(min(k, n - k)):
total_ways = total_ways * (n - i) // (i + 1)
return total_ways
Finally, if you need even larger values and do not mind trading some accuracy, Stirling's approximationis probably the way to go.
最后，如果您需要更大的值并且不介意交易一些准确性，Stirling 的近似值可能是可行的方法。
回答by Vadim Smolyakov
I recommend using dynamic programming (DP) for computing binomial coefficients. In contrast to direct computation, it avoids multiplication and division of large numbers. In addition to recursive solution, it stores previously solved overlapping sub-problems in a table for fast look-up. The code below shows bottom-up (tabular) DP and top-down (memoized) DP implementations for computing binomial coefficients.
我建议使用动态规划 (DP) 来计算二项式系数。与直接计算相比，它避免了大数的乘法和除法。除了递归解决方案之外，它还将先前解决的重叠子问题存储在表中以进行快速查找。下面的代码显示了用于计算二项式系数的自底向上（表格）DP 和自顶向下（记忆化）DP 实现。
def binomial_coeffs1(n, k):
#top down DP
if (k == 0 or k == n):
return 1
if (memo[n][k] != -1):
return memo[n][k]
memo[n][k] = binomial_coeffs1(n-1, k-1) + binomial_coeffs1(n-1, k)
return memo[n][k]
def binomial_coeffs2(n, k):
#bottom up DP
for i in range(n+1):
for j in range(min(i,k)+1):
if (j == 0 or j == i):
memo[i][j] = 1
else:
memo[i][j] = memo[i-1][j-1] + memo[i-1][j]
#end if
#end for
#end for
return memo[n][k]
def print_array(memo):
for i in range(len(memo)):
print('\t'.join([str(x) for x in memo[i]]))
#main
n = 5
k = 2
print("top down DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs1(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
print("bottom up DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs2(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))
Note: the size of the memo table is set to a small value (6) for display purposes, it should be increased if you are computing binomial coefficients for large n and k.
注意：备忘录表的大小设置为一个较小的值 (6) 用于显示目的，如果您正在计算大 n 和 k 的二项式系数，则应该增加它。
回答by Jos Vrancken
It's a good idea to apply a recursive definition, as in Vadim Smolyakov's answer, combined with a DP (dynamic programming), but for the latter you may apply the lru_cache decorator from module functools:
应用递归定义是一个好主意，如 Vadim Smolyakov 的回答，结合 DP（动态编程），但对于后者，您可以应用模块 functools 中的 lru_cache 装饰器：
import functools
@functools.lru_cache(maxsize = None)
def binom(n,k):
if k == 0: return 1
if n == k: return 1
return binom(n-1,k-1)+binom(n-1,k)
回答by assafsha
The simplest way is using the Multiplicative formula. It works for (n,n) and (n,0) as expected.
最简单的方法是使用乘法公式。它按预期适用于 (n,n) 和 (n,0)。
def coefficient(n,k):
c = 1.0
for i in range(1, k+1):
c *= float((n+1-i))/float(i)
return c
