1. ホーム
  2. python

[解決済み】Python 二項係数

2022-02-15 12:50:30

質問

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)  

この二項係数のプログラムは動くが、同じ数を2つ入力すると1になるはずなのに、yがxより大きいときは0になる。

どのように解決するのですか?

この質問は古いのですが、検索結果で上位に来るので指摘しておきます。 scipy には、二項係数を計算するための関数が2つあります。

  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の整数を使用しているので、任意の大きさの結果を扱うことができます!

速度面でも、3つのバージョンで多少異なる結果が得られています。

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 の数値は、上記のように)。