Мне нужно вычислить комбинаторные (nCr) в Python, но я не могу найти функцию для этого в библиотеках math, numpy или stat. Что-то вроде функции типа:
comb = calculate_combinations(n, r)
Мне нужно количество возможных комбинаций, а не фактические комбинации, поэтому itertools.combinations меня не интересует.
Наконец, я хочу избежать использования факториалов, поскольку числа, для которых я буду рассчитывать комбинации, могут стать слишком большими, а факториалы будут чудовищными.
Этот вопрос кажется ДЕЙСТВИТЕЛЬНО легким для ответа, однако меня тонут в вопросах о генерации всех реальных комбинаций, а это не то, чего я хочу.
Смотрите scipy.special.comb (scipy.misc.comb в более старых версиях scipy). При exact является False, то он использует функцию ГАММАНЛОГА, чтобы получить хорошую точность, не принимая много времени. В точном случае он возвращает целое число произвольной точности, которое может занять много времени для вычисления.
Почему бы не написать это самостоятельно? Это однострочный или такой:
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 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() в 10 раз быстрее (тестируется на всех 0 <= (n, k) < 1e3 пары), чем 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
Если вам нужны точные результаты и, попробуйте 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), это было более чем в 10 раз быстрее, чем один вкладыш reduce, предложенный в другом (в настоящее время самом высоком) голосовании. С другой стороны, он не выполняется сниппитом, предоставленным @J.F. Себастьян.
Вот еще одна альтернатива. Это было первоначально написано на С++, поэтому оно может быть обращено к С++ для цепочки конечной точности (например, __int64). Преимущество состоит в том, что (1) он включает только целые операции, и (2) он избегает раздувания целочисленного значения, выполняя последовательные пары умножения и деления. Я проверил результат с треугольником Наса Банова Паскаля, он получил правильный ответ:
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]
Если ваша программа имеет верхнюю границу до 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)
Построение кэша (что делается неявно) занимает до O(N^2) время. Любые последующие вызовы nCr вернутся в O(1).
Вы можете написать 2 простые функции, которые на самом деле оказываются примерно в 5-8 раз быстрее, чем при использовании scipy.special.comb. На самом деле вам не нужно импортировать какие-либо дополнительные пакеты, и функция довольно легко читаема. Хитрость заключается в том, чтобы использовать запоминание для хранения ранее вычисленных значений и использовать определение 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))
Если мы сравним времена
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
Прямая формула дает большие целые числа, когда n больше 20.
Итак, еще один ответ:
from math import factorial
binomial = lambda n,r: reduce(long.__mul__, range(n-r, n+1), 1L) // factorial(r)
короткий, быстрый и эффективный.
Это довольно легко с sympy.
import sympy
comb = sympy.binomial(n, r)
Использование только стандартной библиотеки, распределенной с Python:
import itertools
def nCk(n, k):
return len(list(itertools.combinations(range(n), k)))
Это код @killerT2333, использующий встроенный декоратор напоминаний.
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))
Это возможно так быстро, как вы можете сделать это в чистом питоне для достаточно больших входов:
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
Эта функция очень оптимизирована.
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 3.8, стандартная библиотека теперь включает функцию math.comb для вычисления биномиального коэффициента:
math.comb(n, k)
это количество способов выбрать k элементов из n элементов без повторения n! / (k! (n - k)!):
import math
math.comb(10, 5) # 252
Вот эффективный алгоритм для вас
for i = 1.....r
p = p * ( n - i ) / i
print(p)
Например, nCr (30,7) = факт (30)/(факт (7) * факт (23)) = (30 * 29 * 28 * 27 * 26 * 25 * 24)/(1 * 2 * 3 * 4 * 5 * 6 * 7)
Так что просто запустите цикл от 1 до r, чтобы получить результат.