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

Question

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

comb = calculate_combinations(n, r)

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

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

Это похоже на ДЕЙСТВИТЕЛЬНО простой ответ на вопрос, однако меня тонут в вопросах о создании всех реальных комбинаций, а это не то, чего я хочу.

Answer 1

Это код @ 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))

Answer 2

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

import itertools

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

Answer 3

С симпотами все просто.

import sympy

comb = sympy.binomial(n, r)

Answer 4

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

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

from math import factorial

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

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

Answer 5

Эта функция очень оптимизирована.

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

Answer 6

Начиная с Python 3.8, стандартная библиотека теперь включает функцию math.comb для вычисления биномиального коэффициента:

math.comb (n, k)

- количество способов выбрать k элементов из n элементов без повторений
n! / (k! (n - k)!):

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

Answer 7

Это, вероятно, так же быстро, как вы можете сделать это на чистом питоне для достаточно больших входных данных:

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