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.
2 Answers
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
16 Comments
gorlum0
Why comprehension not just xrange?
leewz
The denominator can be computed using factorial, which is comparable in Python 2 (slightly slower as r increases?) and much faster in Python 3.
Charlie Parker
seriously? There is no standard library that does this, like numpy etc?
dheerosaur
@CharlieParker, Installing numpy is not trivial on many environments. Also, why go to such lengths for such a simple problem?
combinatorist
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. |
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
9 Comments
Mikel
Yeah, but that would be much slower.
Mikel
See stackoverflow.com/questions/3025162/… for better answers, e.g. scipy.comb or gmpy.comb.
Mark Tolonen
For some definition of "slow". If computing poker odds it is perfectly acceptable. The OP didn't specify.
DSM
@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?Mark Tolonen
On my system it takes 10ms to compute
10000 C 500 and returns an answer of 861 digits. Accurate and not particularly "slow" :^) |
import scipy.miscthenscipy.misc.comb(N,k)