Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
A fast way to calculate binomial coefficients in python (Andrew Dalke)
def binomial(n, k):
"""
A fast way to calculate binomial coefficients by Andrew Dalke.
See http://stackoverflow.com/questions/3025162/statistics-combinations-in-python
"""
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in xrange(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0
@keithbriggs

This comment has been minimized.

Copy link

@keithbriggs keithbriggs commented Jan 16, 2020

def binom(n,k): # better version - we don't need two products!
if not 0<=k<=n: return 0
b=1
for t in range(min(k,n-k)):
b*=n; b/=t+1; n-=1
return b

@mbanders

This comment has been minimized.

Copy link

@mbanders mbanders commented Nov 14, 2020

Formatted:

def binomial(n, k):
    if not 0 <= k <= n:
        return 0
    b = 1
    for t in range(min(k, n-k)):
        b *= n
        b /= t+1
        n -= 1
    return int(b)

So for example when you call binomial(5, 2) it returns 10.

@rougier

This comment has been minimized.

Copy link
Owner Author

@rougier rougier commented Nov 15, 2020

You can use b //= t+1 to avoid final cast.

@keithbriggs

This comment has been minimized.

Copy link

@keithbriggs keithbriggs commented Nov 15, 2020

The intention was that this should use only integer arithmetic (my version was converted from C code which used /=). So yes, this is better:

def binomial(n, k):
    if not 0 <= k <= n:
        return 0
    b = 1
    for t in range(min(k, n-k)):
        b *= n
        b //= t+1
        n -= 1
    return b
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment