통계 : 파이썬의 조합

통계 : 파이썬의 조합

---

파이썬에서 combinatorials 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) )

테스트-파스칼의 삼각형 인쇄 :

>>> 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에 대한 것입니다

---

구글 코드에 대한 빠른 검색은 다음을 제공합니다 ( @Mark Byers 's answer의 공식 사용 ).

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, 나는 '의 원래 저자 입니다 ;-) 바이어스.

---

정확한 결과를 원하면을 사용하십시오 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

---

수학적 정의의 리터럴 번역은 많은 경우에 매우 적합합니다 (Python은 자동으로 큰 숫자 산술을 사용함을 기억하십시오).

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이 제공하는 스 니핏에서 성능이 우수합니다.

---

다른 대안이 있습니다. 이것은 원래 C ++로 작성되었으므로 유한 정밀도 정수 (예 : __int64)를 위해 C ++로 백 포트 될 수 있습니다. 장점은 (1) 정수 연산 만 포함하고, (2) 연속적인 곱셈과 나눗셈 쌍을 수행하여 정수 값을 부 풀리지 않도록하는 것입니다. Nas Banov의 파스칼 삼각형으로 결과를 테스트했는데 정답을 얻습니다.

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]

---

If your program has an upper bound to n (say n <= N) and needs to repeatedly compute nCr (preferably for >>N times), using lru_cache can give you a huge performance boost:

from functools import lru_cache

@lru_cache(maxsize=None)
def nCr(n, r):
    return 1 if r == 0 or r == n else nCr(n - 1, r - 1) + nCr(n - 1, r)

Constructing the cache (which is done implicitly) takes up to O(N^2) time. Any subsequent calls to nCr will return in O(1).

---

You can write 2 simple functions that actually turns out to be about 5-8X faster than using scipy.special.comb. In fact, you don't need to import any extra packages, and the function is quite easily readable. The trick is to use memoization to store previously computed values, and using the definition of nCr

# create a memoization dict
memo = {}
def factorial(n):
    """
    Calculate the factorial of an input using memoization
    :param n: int
    :rtype value: int
    """
    if n in [1,0]:
        return 1
    if n in memo:
        return memo[n]
    value = n*fact(n-1)
    memo[n] = value
    return value

def ncr(n, k):
    """
    Choose k elements from a set of n elements - n must be larger than or equal to k
    :param n: int
    :param k: int
    :rtype: int
    """
    return factorial(n)/(factorial(k)*factorial(n-k))

If we compare times

from scipy.special import comb
%timeit comb(100,48)
>>> 100000 loops, best of 3: 6.78 µs per loop

%timeit ncr(100,48)
>>> 1000000 loops, best of 3: 1.39 µs per loop

---

The direct formula produces big integers when n is bigger than 20.

So, yet another response:

from math import factorial

binomial = lambda n,r: reduce(long.__mul__, range(n-r, n+1), 1L) // factorial(r)

short, quick and efficient.

---

It's pretty easy with sympy.

import sympy

comb = sympy.binomial(n, r)

---

Using only standard library distributed with Python:

import itertools

def nCk(n, k):
    return len(list(itertools.combinations(range(n), k)))

---

This is @killerT2333 code using the builtin memoization decorator.

from functools import lru_cache

@lru_cache()
def factorial(n):
    """
    Calculate the factorial of an input using memoization
    :param n: int
    :rtype value: int
    """
    return 1 if n in (1, 0) else n * factorial(n-1)

@lru_cache()
def ncr(n, k):
    """
    Choose k elements from a set of n elements,
    n must be greater than or equal to k.
    :param n: int
    :param k: int
    :rtype: int
    """
    return factorial(n) / (factorial(k) * factorial(n - k))

print(ncr(6, 3))

---

That's probably as fast as you can do it in pure python for reasonably large inputs:

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

---

This function is very optimazed.

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

---

Starting Python 3.8, the standard library now includes the math.comb function to compute the binomial coefficient:

math.comb(n, k)

which is the number of ways to choose k items from n items without repetition
n! / (k! (n - k)!):

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

---

Here is an efficient algorithm for you

for i = 1.....r

   p = p * ( n - i ) / i

print(p)

For example nCr(30,7) = fact(30) / ( fact(7) * fact(23)) = ( 30 * 29 * 28 * 27 * 26 * 25 * 24 ) / (1 * 2 * 3 * 4 * 5 * 6 * 7)

So just run the loop from 1 to r can get the result.

참고URL : https://stackoverflow.com/questions/3025162/statistics-combinations-in-python