Binominal coefficient in python-CodePudding

so I was wondering how i could get around this problem where i have this code

    #defining a function that computes the factorial of an integer

def fac(b):
 if b==1:
    return 1
else:
    return b * fac(b-1)

#takes two integers and does the binomial coefficient operand

def combinations(n,k):
    result = (fac(n)) / (fac(k) * fac(n-k))
    return result

n=10
k=2

print(combinations(n,k))

and using it to (nCk) large numbers such as (1000,700) without using the

 sys.setreccursionlimit(x)

for example. can i somehow remove the lowest values in (6C3) so it just calculates (6x5x4)/(3x2x1) since 6! is 6x5x4x3x2x1 and 3! is 3x2x1. and the formula is n!/(k!x(n-k)!)

and therefore lowering the amounts of recursions happening

CodePudding user response：

I feel you're kind of trying to reinvent the wheel here. This functionality already exists in the built-in math module, and it's quite efficient:

>>> import math
>>> math.comb(1000, 700)
542825004640614064815358503892902599588060075560435179852301016412253602009800031872232761420804306539976220810204913677796961128392686442868524741815732892024613137013599170443939815681313827516308854820419235457578544489551749630302863689773725905288736148678480

CodePudding user response：

You can use the cache decorator (docs, nice video tutorial)

from functools import cache

@cache
def fac(b):
    return b * fac(b-1) if b else 1

def combinations(n,k):
    M = max(n,k)
    for i in range(M):
        fac(i)
    return (fac(n)) // (fac(k) * fac(n-k))


n=1000
k=700
print(combinations(n,k))

Output

542825004640614064815358503892902599588060075560435179852301016412253602009800031872232761420804306539976220810204913677796961128392686442868524741815732892024613137013599170443939815681313827516308854820419235457578544489551749630302863689773725905288736148678480

CodePudding user response：

Factorial

Recursion is great in some languages, but absolutely sucks in python. Do not use recursion in python unless you have a very good reason to.

For your factorial function, I suggest using a simple loop:

def factorial(n):
    result = 1
    for k in range(2,n 1):
        result *= k
    return result

Or you can use the prod function to compute the product of the range directly:

from math import prod

def factorial(n):
    return prod(range(2, n 1))

Or you can use the existing factorial function directly:

from math import factorial

Binomial coefficient

Mathematicians like to "compress" the formula of the binomial coefficient as (n choose k) = factorial(n) / (factorial(k) * factorial(n-k)), but this formula is inefficient for no good reason if used directly. Remember that all the factors in factorial(n-k) cancel out with the lower factors from factorial(n). So, there is no need to compute the product of these factors at all.

Instead you can at least do this small optimisation:

def binomial(n, k):
    a, b = (k, n-k) if k < n-k else (n-k, k)
    numerator = 1
    for i in range(b 1, n 1):
        numerator *= i
    return numerator / factorial(a)

Of course you can use the existing function comb directly:

from math import comb