0

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

Improve this question
1

3 Answers 3

Reset to default
2

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
Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

haha thats kind of the point, i dont want to use any inbuilt functions to solve this.
@LAXENOSUND keep in mind that Pythons inbuilt functions are written in C, which always makes them (much) faster than a pure Python solution.
@Damiaan oh, thanks thats good to know however i was just curiuos how this problem would be solved with just classic "functions" without having speed in mind.
Damiaan is exactly right, you can have a look at the math implementation in CPython and see how C(n, k) is computed, but don't expect to top that.
1

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
Improve this answer

Comments

1

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
Improve this answer

5 Comments

This still results in RecursionError.
Add this two lines before the last one M = max(n,k), for i in range(M): fac(i). This plus the cache decorator will work (I modified my original answer)
Even so, the answer is not technically correct as it's lost precision due to the e+263
The division operator you should use in combinations is //, not the / that you're using now. // is exact integer division, and the theory guarantees that (fac(k) * fac(n-k)) is a divisor of fac(n).
@PresidentJamesK.Polk is right! Updated my answer

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.