Биномиальный коэффициент Python

Ответ 1

Этот вопрос старый, но, поскольку он поднимается высоко над результатами поиска, я scipy, что у scipy есть две функции для вычисления биномиальных коэффициентов:

1. scipy.special.binom()

2. scipy.special.comb()

   import scipy.special
   
   # the two give the same results 
   scipy.special.binom(10, 5)
   # 252.0
   scipy.special.comb(10, 5)
   # 252.0
   
   scipy.special.binom(300, 150)
   # 9.375970277281882e+88
   scipy.special.comb(300, 150)
   # 9.375970277281882e+88
   
   # ...but with 'exact == True'
   scipy.special.comb(10, 5, exact=True)
   # 252
   scipy.special.comb(300, 150, exact=True)
   # 393759702772827452793193754439064084879232655700081358920472352712975170021839591675861424
   

Обратите внимание, что scipy.special.comb(exact=True) использует целые числа Python, и поэтому он может обрабатывать произвольно большие результаты!

По скорости три версии дают несколько разные результаты:

num = 300

%timeit [[scipy.special.binom(n, k) for k in range(n + 1)] for n in range(num)]
# 52.9 ms ± 107 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

%timeit [[scipy.special.comb(n, k) for k in range(n + 1)] for n in range(num)]
# 183 ms ± 814 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)each)

%timeit [[scipy.special.comb(n, k, exact=True) for k in range(n + 1)] for n in range(num)]
# 180 ms ± 649 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

(и для n = 300, биномиальные коэффициенты слишком велики, чтобы быть правильно представленными с использованием чисел с float64, как показано выше).

Ответ 2

Вот версия, которая на самом деле использует правильную формулу. :)

#! /usr/bin/env python

''' Calculate binomial coefficient xCy = x! / (y! (x-y)!)
'''

from math import factorial as fac


def binomial(x, y):
    try:
        binom = fac(x) // fac(y) // fac(x - y)
    except ValueError:
        binom = 0
    return binom


#Print Pascal triangle to test binomial()
def pascal(m):
    for x in range(m + 1):
        print([binomial(x, y) for y in range(x + 1)])


def main():
    #input = raw_input
    x = int(input("Enter a value for x: "))
    y = int(input("Enter a value for y: "))
    print(binomial(x, y))


if __name__ == '__main__':
    #pascal(8)
    main()

...

Вот альтернативная версия binomial() я написал несколько лет назад, в которой не используется math.factorial(), которой не было в старых версиях Python. Однако он возвращает 1, если r не находится в диапазоне (0, n + 1).

def binomial(n, r):
    ''' Binomial coefficient, nCr, aka the "choose" function 
        n! / (r! * (n - r)!)
    '''
    p = 1    
    for i in range(1, min(r, n - r) + 1):
        p *= n
        p //= i
        n -= 1
    return p

Ответ 3

Итак, этот вопрос возникает первым, если вы ищете "Реализовать биномиальные коэффициенты в Python". Только этот ответ во второй части содержит эффективную реализацию, основанную на мультипликативной формуле. Эта формула выполняет минимальное количество умножений. Приведенная ниже функция не зависит от каких-либо встроенных функций или импорта:

def fcomb0(n, k):
    '''
    Compute the number of ways to choose $k$ elements out of a pile of $n.$

    Use an iterative approach with the multiplicative formula:
    $$\frac{n!}{k!(n - k)!} =
    \frac{n(n - 1)\dots(n - k + 1)}{k(k-1)\dots(1)} =
    \prod_{i = 1}^{k}\frac{n + 1 - i}{i}$$

    Also rely on the symmetry: $C_n^k = C_n^{n - k},$ so the product can
    be calculated up to $\min(k, n - k).$

    :param n: the size of the pile of elements
    :param k: the number of elements to take from the pile
    :return: the number of ways to choose k elements out of a pile of n
    '''

    # When k out of sensible range, should probably throw an exception.
    # For compatibility with scipy.special.{comb, binom} returns 0 instead.
    if k < 0 or k > n:
        return 0

    if k == 0 or k == n:
        return 1

    total_ways = 1
    for i in range(min(k, n - k)):
        total_ways = total_ways * (n - i) // (i + 1)

    return total_ways

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

Ответ 4

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

math.comb(n, k)

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

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

Ответ 5

Ваша программа продолжит выполнение второго оператора if в случае y == x, вызвав ZeroDivisionError. Вы должны сделать утверждения взаимоисключающими; способ сделать это - использовать elif ( "else if" ) вместо if:

import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == x:
    print(1)
elif y == 1:         # see georg comment
    print(x)
elif y > x:          # will be executed only if y != 1 and y != x
    print(0)
else:                # will be executed only if y != 1 and y != x and x <= y
    a = math.factorial(x)
    b = math.factorial(y)
    c = math.factorial(x-y)  # that appears to be useful to get the correct result
    div = a // (b * c)
    print(div)  

Ответ 6

Вот функция, которая рекурсивно вычисляет биномиальные коэффициенты, используя условные выражения

def binomial(n,k):
    return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1))

Ответ 7

Для Python 3 у scipy есть функция scipy.special.comb, которая может генерировать с плавающей точкой, а также точные целочисленные результаты

import scipy.special

res = scipy.special.comb(x, y, exact=True)

Смотрите документацию для scipy.special.comb.

Для Python 2 функция находится в scipy.misc, и она работает одинаково:

import scipy.misc

res = scipy.misc.comb(x, y, exact=True)

Ответ 8

Как насчет этого?:) Он использует правильную формулу, избегает math.factorial и принимает меньше операций умножения:

import math
import operator
product = lambda m,n: reduce(operator.mul, xrange(m, n+1), 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(y+1, x) / product(1, x-y)

Кроме того, чтобы избежать арифметики с большими целыми числами, вы можете использовать числа с плавающей запятой, конвертировать product(a[i])/product(b[i]) до product(a[i]/b[i]) и перепишите вышеуказанную программу как:

import math
import operator
product = lambda iterable: reduce(operator.mul, iterable, 1)
x = max(0, int(input("Enter a value for x: ")))
y = max(0, int(input("Enter a value for y: ")))
print product(map(operator.truediv, xrange(y+1, x+1), xrange(1, x-y+1)))

Ответ 9

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

def binomial_coeffs1(n, k):
    #top down DP
    if (k == 0 or k == n):
        return 1
    if (memo[n][k] != -1):
        return memo[n][k]

    memo[n][k] = binomial_coeffs1(n-1, k-1) + binomial_coeffs1(n-1, k)
    return memo[n][k]

def binomial_coeffs2(n, k):
    #bottom up DP
    for i in range(n+1):
        for j in range(min(i,k)+1):
            if (j == 0 or j == i):
                memo[i][j] = 1
            else:
                memo[i][j] = memo[i-1][j-1] + memo[i-1][j]
            #end if
        #end for
    #end for
    return memo[n][k]

def print_array(memo):
    for i in range(len(memo)):
        print('\t'.join([str(x) for x in memo[i]]))

#main
n = 5
k = 2

print("top down DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs1(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))

print("bottom up DP")
memo = [[-1 for i in range(6)] for j in range(6)]
nCk = binomial_coeffs2(n, k)
print_array(memo)
print("C(n={}, k={}) = {}".format(n,k,nCk))

Примечание: размер таблицы памятки для отображения установлен на небольшое значение (6), его следует увеличить, если вы вычисляете биномиальные коэффициенты для больших n и k.

Ответ 10

Самый простой способ - использовать формулу Multiplicative. Это работает для (n, n) и (n, 0), как и ожидалось.

def coefficient(n,k):
    c = 1.0
    for i in range(1, k+1):
        c *= float((n+1-i))/float(i)
    return c

Мультипликативная формула

Ответ 11

Немного сокращенный мультипликативный вариант, заданный PM 2Ring и alisianoi. Работает с Python 3 и не требует никаких пакетов.

def comb(n, k):
  # Remove the next two lines is out-of-range check is not needed
  if k < 0 or k > n:
    return None
  x = 1
  for i in range(min(k, n - k)):
    x = x*(n - i)//(i + 1)
  return x

Или

from functools import reduce
def comb(n, k):
  return (None if k < 0 or k > n else
    reduce(lambda x, i: x*(n - i)//(i + 1), range(min(k, n - k)), 1))

Деление выполняется сразу после умножения, чтобы не накапливать большие числа.

Ответ 12

Было бы неплохо применить рекурсивное определение, как в ответе Вадима Смолякова, в сочетании с DP (динамическое программирование), но для последнего вы можете применить декоратор lru_cache из модуля functools:

import functools

@functools.lru_cache(maxsize = None)
def binom(n,k):
    if k == 0: return 1
    if n == k: return 1
    return binom(n-1,k-1)+binom(n-1,k)