Is there a math nCr function in Python? [duplicate]

Question

Is there a built-in nCr (n choose r) function included in the Python math library like the one shown below?

I understand that the computation can be programmed, but I thought I'd check to see if it's built-in before I do.

Lorenzo

#2097073 – Hypnotherapy

Can Itertools helps you (docs.python.org/library/itertools.html) – Fireplace

The duplicate is what I went with... works great. – Lorenzo

You may find sympy.binomial useful. – Unsteel

scipy has a function for this: import scipy.misc then scipy.misc.comb(N,k) – Projectile

import scipy.misc scipy.special.comb(10,5) – Hm

If you need to do this in a loop, then you may be better off using pascals triangle. – Jeans

@TylerHeers, you'd think so, but nope. The walrus operator is only available in 3.8, but you can roll this: twitter.com/raymondh/status/1139633938572251136 into a loop and get an O(n) calculation of the nth row of Pascal's triangle. – Clipclop

Answer 1

On Python 3.8+, use math.comb:

>>> from math import comb
>>> comb(10, 3)
120

For older versions of Python, you can use the following program:

import operator as op
from functools import reduce

def ncr(n, r):
    r = min(r, n-r)
    numer = reduce(op.mul, range(n, n-r, -1), 1)
    denom = reduce(op.mul, range(1, r+1), 1)
    return numer // denom  # or / in Python 2

Baleful

Why comprehension not just xrange? – Unsteel

The denominator can be computed using factorial, which is comparable in Python 2 (slightly slower as r increases?) and much faster in Python 3. – Midgut

is it better to import operator than to use lambda x,y: x*y ? – Ragout

@Netzsooc: op.mul is approximately 25% faster in my quick timing test I did on my computer. YMMV. – Pursue

seriously? There is no standard library that does this, like numpy etc? – Wrench

@CharlieParker, Installing numpy is not trivial on many environments. Also, why go to such lengths for such a simple problem? – Baleful

If you want to handle impossible scenario's (r< 0 or r > n), then and: if r < 0: return 0 after reseting r to the min. – Cumulous

I thought this might be handled by the empty xrange functions, but then reduce errors out because it does not know the initial value (and even then, the value should be 1 for multiplication, which won't give you the correct answer of 0). – Cumulous

why min(r, n - r)? – Weltschmerz

@Weltschmerz For performance. ncr(n, r) is equal to ncr(n, n-r) – Baleful

Your function does not work perfectly for big numbers. I've used it with n = 100 and k = 18 and it returned 3.066451080298821e+19 (also written as 30664510802988208128) whereas the correct answer is 30664510802988208300. You can correct this with numer // denom instead of numer / denom. It will return the result as an integer division instead of a floating point one. I think this behaviour is caused by the lack of precision of a float number. – Colored

@Colored '/' is integer division in python 2, which is the first snippet written in. – Blurt

Why did this have to wait till Python 3.8? O.o – Rundle

Any idea to do this for permutation? The denum part of this answer is great. – Howlet

I would move the python 3.8 answer to the top, since that will be the best solution for most people from now on. – Saith

scipy.special.comb for older python versions – Pease

Answer 2

Do you want iteration? Use itertools.combinations. Common usage:

>>> import itertools
>>> itertools.combinations('abcd', 2)
<itertools.combinations object at 0x104e9f010>
>>> list(itertools.combinations('abcd', 2))
[('a', 'b'), ('a', 'c'), ('a', 'd'), ('b', 'c'), ('b', 'd'), ('c', 'd')]
>>> [''.join(x) for x in itertools.combinations('abcd', 2)]
['ab', 'ac', 'ad', 'bc', 'bd', 'cd']

If you just need to compute the formula, math.factorial can be used, but is not fast for large combinations, but see math.comb below for an optimized calculation available in Python 3.8+:

import math

def ncr(n, r):
    f = math.factorial
    return f(n) // f(r) // f(n-r)

print(ncr(4, 2))  # Output: 6

As of Python 3.8, math.comb can be used and is much faster:

>>> import math
>>> math.comb(4,2)
6

Comp

Yeah, but that would be much slower. – Hypnotherapy

See #3025662 for better answers, e.g. scipy.comb or gmpy.comb. – Hypnotherapy

For some definition of "slow". If computing poker odds it is perfectly acceptable. The OP didn't specify. – Comp

@Renato: what are you talking about? This answer isn't dangerous at all. Do you think that math.factorial returns a float, and not an arbitrary-precision integer, maybe? – Pascia

On my system it takes 10ms to compute 10000 C 500 and returns an answer of 861 digits. Accurate and not particularly "slow" :^) – Comp

@RichardFung If we assume that the divisions are integer division (the case in python2, and hopefully the case given that we're doing combinatorics) then that will return 0 for any case with n < r. As a simple proof, factorial is monotonic, therefore if n < r then f(n) < f(r), for any a < b a/b is 0 (for integer division). – Characterization

@Characterization You're completely right, I've deleted the comment. – Commendation

With Python 3 running this with (6000000, 2). it takes quite a while, not to mention it throws an Overflown error unless you add //. Accepted answer by far faster. – Giveaway

scipy.special.comb for older python versions – Pease