Python에서 조합 (nCr)을 계산해야하지만 math, numpy또는 stat 라이브러리 에서이를 수행 할 함수를 찾을 수 없습니다 . 유형의 함수와 같은 것 :
comb = calculate_combinations(n, r)실제 조합이 아닌 가능한 조합의 수가 필요하므로 itertools.combinations관심이 없습니다.
마지막으로, 조합을 계산할 숫자가 너무 커지고 팩토리얼이 엄청나게 클 수 있으므로 팩토리얼 사용을 피하고 싶습니다.
이것은 정말 대답하기 쉬운 질문처럼 보이지만 내가 원하는 것이 아닌 모든 실제 조합을 생성하는 것에 대한 질문에 빠져 있습니다.
답변
scipy.special.comb (이전 버전의 scipy에서는 scipy.misc.comb)를 참조하십시오 . 때 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) )테스트-Pascal의 삼각형 인쇄 :
>>> 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
>>> 추신. 대체 편집 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))그렇게하지 ERR 큰 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 0choose()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, 나는 ‘의 원래 저자 입니다 😉 바이어스.
답변
정확한 결과를 원하면 sympy.binomial. 가장 빠른 방법 인 것 같습니다.
x = 1000000
y = 234050
%timeit scipy.misc.comb(x, y, exact=True)
1 loops, best of 3: 1min 27s per loop
%timeit gmpy.comb(x, y)
1 loops, best of 3: 1.97 s per loop
%timeit int(sympy.binomial(x, y))
100000 loops, best of 3: 5.06 µs per loop답변
수학적 정의를 문자 그대로 번역하면 많은 경우에 매우 적합합니다 (파이썬이 자동으로 큰 숫자 산술을 사용한다는 점을 기억하십시오).
from math import factorial
def calculate_combinations(n, r):
return factorial(n) // factorial(r) // factorial(n-r)내가 테스트 한 일부 입력 (예 : n = 1000 r = 500)의 경우 이것은 reduce다른 (현재 가장 많이 득표 한) 답변에서 제안 된 한 라이너보다 10 배 이상 빠릅니다 . 반면에 @JF Sebastian이 제공하는 스 니핏보다 성능이 뛰어납니다.
답변
시작 Python 3.8하면 표준 라이브러리 math.comb에 이항 계수를 계산하는 함수가 포함됩니다 .
math.comb (n, k)
반복하지 않고 n 항목에서 k 항목을 선택하는 방법의 수입니다 n! / (k! (n - k)!).
import math
math.comb(10, 5) # 252