import math
x = int(input("Enter a value for x: "))
y = int(input("Enter a value for y: "))
if y == 1 or y == x:
print(1)
if y > x:
print(0)
else:
a = math.factorial(x)
b = math.factorial(y)
div = a // (b*(x-y))
print(div)
Эта программа с биномиальным коэффициентом работает, но когда я ввожу два одинаковых числа, которые, как предполагается, равны 1, или когда y больше, чем x, оно должно равняться 0
Этот вопрос старый, но, поскольку он поднимается высоко над результатами поиска, я scipy, что у scipy есть две функции для вычисления биномиальных коэффициентов:
scipy.special.binom()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, как показано выше).
Вот версия, которая на самом деле использует правильную формулу. :)
#! /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
Итак, этот вопрос возникает первым, если вы ищете "Реализовать биномиальные коэффициенты в 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
Наконец, если вам нужны еще большие значения и вы не против торговать с какой-то точностью, возможно, вам подходит приближение Стирлинга.
Обратите внимание, что начиная с 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
Ваша программа продолжит выполнение второго оператора 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)
Вот функция, которая рекурсивно вычисляет биномиальные коэффициенты, используя условные выражения
def binomial(n,k):
return 1 if k==0 else (0 if n==0 else binomial(n-1, k) + binomial(n-1, k-1))
Для 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)
Как насчет этого?:) Он использует правильную формулу, избегает 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)))
Я рекомендую использовать динамическое программирование (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.
Самый простой способ - использовать формулу 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
Немного сокращенный мультипликативный вариант, заданный 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))
Деление выполняется сразу после умножения, чтобы не накапливать большие числа.
Было бы неплохо применить рекурсивное определение, как в ответе Вадима Смолякова, в сочетании с 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)