巨蟒二项式系数

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)

这个二项式系数程序可以工作，但是当我输入两个相同的数字，它们应该等于1，或者当 y 大于 x 时，它们应该等于0。

179206 次浏览
小开

在 y == x的情况下，您的程序将继续执行第二个 if语句，从而导致 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)
小开

这个版本实际上使用了 正确的配方。 :)

#! /usr/bin/env python


''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''


from math import factorial as fac




def binomial(x, y):
try:
return fac(x) // fac(y) // fac(x - y)
except ValueError:
return 0




#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()

...

这是我几年前编写的 binomial()的另一个版本，它没有使用 math.factorial()，而在旧版本的 Python 中也没有 math.factorial()。但是，如果 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
小开

这个怎么样? :)它使用正确的公式，避免了 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)

另外，为了避免使用大整数算法，您可以使用浮点数，转换 从 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)))
小开
最佳答案

这个问题已经过时了，但是当它在搜索结果中出现的时候，我会指出 scipy有两个计算二项式系数的函数:

  1. scipy.special.binom()

  2. scipy.special.comb()

    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!

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)

(对于 n = 300，二项式系数太大，无法正确使用 float64数字表示，如上所示)。

小开

下面是一个函数，它使用条件表达式递归地计算二项式系数

def binomial(n,k):
return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1))
小开

对于 Python 3，scypy 有一个函数 scypy.specal.comb，它可以产生浮点数和精确的整数结果

import scipy.special


res = scipy.special.comb(x, y, exact=True)

请参阅 特别的梳子的文档。

对于 Python 2，该函数位于 scypy.misc 中，它的工作方式是相同的:

import scipy.misc


res = scipy.misc.comb(x, y, exact=True)
小开

因此，如果搜索“在 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

最后，如果你需要更大的价值，并不介意交易一些准确性，斯特林近似可能是走的方式。

小开

我推荐使用动态规划(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))

注意: 备注表的大小被设置为一个小值(6)用于显示目的，如果你计算大 n 和 k 的二项式系数，它应该被增加。

小开

应用一个递归定义是个好主意，就像瓦迪姆 · 斯莫利亚科夫(Vadim Smolyakov)的回答，结合一个 DP (动态编程) ，但是对于后者，你可以应用来自 module function tools 的 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)
小开

最简单的方法是使用乘法公式，它适用于(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

乘法公式

小开

注意，从 Python 3.8开始，标准库提供了计算二项式系数的 math.comb函数:

Comb (n，k)

这是从 n 个项目中选择 k 个项目而不重复的方法的数量 < br > n! / (k! (n - k)!):

import math
math.comb(10, 5)  # 252
math.comb(10, 10) # 1
小开

由 PM 2 Ring和 阿利西亚诺伊提供的一个比特缩短的乘法变体。与 python3一起工作，不需要任何包。

def comb(n, k):
# Remove the next two lines if out-of-range check is not needed
if k < 0 or k > n:
return None
x = 1
for i in range(min(k, n - k)):
x = x*(n - i)//(i + 1)
return x

或者

from functools import reduce
def comb(n, k):
return (None if k < 0 or k > n else
reduce(lambda x, i: x*(n - i)//(i + 1), range(min(k, n - k)), 1))

除法是在乘法后立即进行的，以避免累积较高的数字。

小开

对于每一个寻找二项式系数的 记录(西亚诺称之为 binomln)的人来说，这个答案拥有它:

from numpy import log
from scipy.special import betaln


def binomln(n, k):
"Log of scipy.special.binom calculated entirely in the log domain"
return -betaln(1 + n - k, 1 + k) - log(n + 1)

(如果你的语言/库没有 betaln，但是有 gammaln，像 Go 一样，不要害怕，因为 betaln(a, b)只是 gammaln(a) + gammaln(b) - gammaln(a + b)，每 数学世界。)

小开 
import math


def binomial_coefficients(n,k):
product = 1
for i in range(k):
product = math.floor(((product * (n - i))/(i + 1))
return product

在计算二项式系数时，不应该计算(n，k)和 k 的有限乘积 n (n-1) ... (n-k + 1) ！.这可能会导致溢出错误。因此，利用一点数论，我们可以假设输入总是整数形式(因为(n，k)的组合只接受整数) ，我们可以看到，对于连续整数的乘积中的整数‘ i’，乘积中的任何术语 u 总是可以被 i 整除。

注意: 您可以在不导入数学模块的情况下完成此操作. math.floor (a/b)等价于 a//b


提交答案