mathPython でコンビナトリアル (nCr) を計算する必要がありますが、それを実行する関数が、numpyまたはstat ライブラリで見つかりません。タイプの関数のようなもの：
comb = calculate_combinations(n, r)
実際の組み合わせではなく、可能な組み合わせの数が必要なので、itertools.combinations興味がありません。
最後に、階乗の使用を避けたいと思います。組み合わせを計算する数値が大きくなりすぎて、階乗が巨大になる可能性があるためです。
これは非常に簡単に答えられる質問のように思えますが、実際のすべての組み合わせを生成することについての質問に溺れています。これは私が望んでいるものではありません。
scipy.special.comb（古いバージョンのscipyではscipy.misc.comb）を参照してください。がFalseの場合exact、gammaln関数を使用して、時間をかけずに優れた精度を取得します。正確な場合、任意精度の整数が返され、計算に時間がかかる場合があります。
自分で書いてみませんか？それはワンライナーなどです：
from operator import mul # or mul=lambda x,y:x*y
from fractions import Fraction
def nCk(n,k):
return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
テスト - パスカルの三角形の出力:
>>> for n in range(17):
... print ' '.join('%5d'%nCk(n,k) for k in range(n+1)).center(100)
...
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
>>>
PS。に置き換えるように編集されてint(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1)))
いるint(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))ため、大きな N/K に対してエラーが発生することはありません
Googleコードをすばやく検索すると、次のようになります（@Mark Byersの回答の式を使用します）：
def choose(n, k):
"""
A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
"""
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in xrange(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0
choose()scipy.misc.comb()正確な答えが必要な場合よりも 10 倍高速です (すべての 0 <= (n,k) < 1e3 ペアでテスト) 。
def comb(N,k): # from scipy.comb(), but MODIFIED!
if (k > N) or (N < 0) or (k < 0):
return 0L
N,k = map(long,(N,k))
top = N
val = 1L
while (top > (N-k)):
val *= top
top -= 1
n = 1L
while (n < k+1L):
val /= n
n += 1
return val
正確な結果と速度が必要な場合は、 gmpyを試してください-gmpy.comb要求どおりに実行する必要があり、かなり高速です（もちろん、gmpyの元の作成者として、私は偏見があります;-)。
多くの場合、数学的な定義の文字通りの翻訳は非常に適切です (Python は自動的に大きな数の演算を使用することを思い出してください)。
from math import factorial
def calculate_combinations(n, r):
return factorial(n) // factorial(r) // factorial(n-r)
reduce私がテストしたいくつかの入力 (例: n=1000 r=500) では、これは別の (現在最も投票数の多い) 回答で提案されているライナーよりも 10 倍以上高速でした。一方で、@JF Sebastian が提供するスニピットよりもパフォーマンスが優れています。
別の方法があります。これは元々C++で書かれていたので、有限精度の整数（__int64など）のためにC++にバックポートすることができます。利点は、（1）整数演算のみを含み、（2）乗算と除算の連続ペアを実行することにより、整数値の肥大化を回避することです。NasBanovのパスカルの三角形で結果をテストしました。正解は次のとおりです。
def choose(n,r):
"""Computes n! / (r! (n-r)!) exactly. Returns a python long int."""
assert n >= 0
assert 0 <= r <= n
c = 1L
denom = 1
for (num,denom) in zip(xrange(n,n-r,-1), xrange(1,r+1,1)):
c = (c * num) // denom
return c
理論的根拠：乗算と除算の数を最小限に抑えるために、式を次のように書き直します。
n! n(n-1)...(n-r+1)
--------- = ----------------
r!(n-r)! r!
乗算のオーバーフローを可能な限り回避するために、左から右に次のSTRICTの順序で評価します。
n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r
この順序で操作される整数算術が正確であることを示すことができます（つまり、丸め誤差はありません）。
動的計画法を使用すると、時間の計算量は Θ(n*m) で、空間の計算量は Θ(m) になります。
def binomial(n, k):
""" (int, int) -> int
| c(n-1, k-1) + c(n-1, k), if 0 < k < n
c(n,k) = | 1 , if n = k
| 1 , if k = 0
Precondition: n > k
>>> binomial(9, 2)
36
"""
c = [0] * (n + 1)
c[0] = 1
for i in range(1, n + 1):
c[i] = 1
j = i - 1
while j > 0:
c[j] += c[j - 1]
j -= 1
return c[k]
sympy を使えば簡単です。
import sympy
comb = sympy.binomial(n, r)
Python で配布されている標準ライブラリのみを使用:
import itertools
def nCk(n, k):
return len(list(itertools.combinations(range(n), k)))
この機能は非常に最適化されています。
def nCk(n,k):
m=0
if k==0:
m=1
if k==1:
m=n
if k>=2:
num,dem,op1,op2=1,1,k,n
while(op1>=1):
num*=op2
dem*=op1
op1-=1
op2-=1
m=num//dem
return m
それはおそらく、かなり大きな入力に対して純粋な python で実行できるのと同じくらい高速です。
def choose(n, k):
if k == n: return 1
if k > n: return 0
d, q = max(k, n-k), min(k, n-k)
num = 1
for n in xrange(d+1, n+1): num *= n
denom = 1
for d in xrange(1, q+1): denom *= d
return num / denom