Python二项式系数

Question

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.如果有人可以帮助我,程序需要稍微调整一下

Answer 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
   

注意,scipy.special.comb(exact=True)使用Python整数,因此它可以处理任意大的结果!

速度方面,三个版本给出了不同的结果:

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数字正确表示,如上所示).

Answer 2

这是一个实际使用正确公式的版本.:)

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

...

这是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

Answer 3

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

最后，如果您需要更大的值并且不介意交易一些准确性，Stirling 的近似值可能是可行的方法。

Answer 4

请注意，开始Python 3.8，标准库提供了math.comb计算二项式系数的功能：

math.comb（n，k）

这是从n个项中不重复选择k个项的方法的数量
n! / (k! (n - k)!)：

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