Статистика: комбинации в Python

мне нужно вычислить комбинаторики (nCr) в Python, но не могу найти функцию, чтобы сделать это в math,numpy или stat библиотеки. Что-то вроде функции типа:



comb = calculate_combinations(n, r)


мне нужно количество возможных комбинаций, а не реальные комбинации, так itertools.combinations меня не интересует.



наконец, я хочу избежать использования факториалов, так как числа, для которых я буду вычислять комбинации, могут стать слишком большими, и факториалы будут уродливый.



это кажется очень легко ответить на вопрос, однако я тону в вопросах о создании всех фактических комбинаций, что не то, что я хочу. :)



большое спасибо

641   13  

13 ответов:

посмотреть scipy.специальный.гребень (scipy.разное.расчески в старых версиях составляющей). Когда exact является ложным, он использует функцию gammaln для получения хорошей точности, не занимая много времени. В точном случае он возвращает целое число произвольной точности, которое может занять много времени для вычисления.

95  
2017-12-04 19:24:58

Почему бы не написать его самостоятельно? Это однострочный или такой:

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

101  
2013-09-17 04:13:08

быстрый поиск по коду Google дает (он использует формулу от @ ответ Марка Байерса):

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() в 10 раз быстрее (проверено на всех 0 scipy.misc.comb() Если вам нужен точный ответ.

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
44  
2017-05-23 14:46:49

Если вы хотите получить точные результаты и скорость, попробовать gmpy--gmpy.comb должны делать именно то, что вы просите, и это довольно быстро (конечно, как gmpy оригинальный автор, я am предвзят;-).

40  
2010-06-12 00:15:40

Если вы хотите получить точный результат, используйте 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
23  
2013-11-23 14:56:36

буквальный перевод математического определения вполне адекватен во многих случаях (помня, что Python автоматически будет использовать арифметику больших чисел):

from math import factorial

def calculate_combinations(n, r):
    return factorial(n) // factorial(r) // factorial(n-r)

для некоторых входов, которые я тестировал (например, n=1000 r=500) это было более чем в 10 раз быстрее, чем один лайнер reduce предлагается в другом (в настоящее время самый высокий голос) ответ. С другой стороны, он выполняется фрагментом, предоставленным @J. F. Sebastian.

18  
2013-11-26 08:25:15

вот еще один вариант. Этот был первоначально написан на C++, поэтому его можно вернуть на C++ для целого числа конечной точности (например, __int64). Преимущество заключается в том, что (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!

чтобы избежать переполнения умножения как можно больше, мы будем оценивать в следующем строгом порядке, слева направо:

n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r

мы можем показать, что целочисленная арифметика, работающая в этом порядке, является точной (т. е. без ошибки округления).

9  
2012-08-24 22:29:45

используя динамическое программирование, временная сложность Θ (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]
4  
2014-09-12 20:30:10

если ваша программа имеет верхнюю границу n (скажем n <= N) и необходимо повторно вычислить nCr (предпочтительно для >>N раза), используя lru_cache можем дать вам огромный прирост производительности:

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)

построение кэша (которое выполняется неявно) занимает до

2  
2017-04-30 17:41:45

прямая формула дает большие целые числа, когда n больше 20.

Итак, еще один ответ:

from math import factorial

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

короткий, быстрый и эффективный.

1  
2015-12-04 13:46:38

Это довольно легко с sympy.

import sympy

comb = sympy.binomial(n, r)
1  
2016-07-17 21:21:07

Это, вероятно, так же быстро, как вы можете сделать это в чистом 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
0  
2015-05-24 23:42:25

используя только стандартная библиотека, распространяемая с Python:

import itertools

def nCk(n, k):
    return len(list(itertools.combinations(range(n), k)))
0  
2016-11-11 00:29:34

Comments

    Ничего не найдено.
Click here to cancel reply.