310

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

n choose k formula

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

8

2 Answers 2

385

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
  • 2
    Why comprehension not just xrange?
    – gorlum0
    Feb 9, 2011 at 7:50
  • 4
    The denominator can be computed using factorial, which is comparable in Python 2 (slightly slower as r increases?) and much faster in Python 3.
    – leewz
    Feb 1, 2014 at 20:47
  • 4
    seriously? There is no standard library that does this, like numpy etc? Sep 5, 2017 at 19:25
  • 6
    @CharlieParker, Installing numpy is not trivial on many environments. Also, why go to such lengths for such a simple problem?
    – dheerosaur
    Sep 15, 2017 at 5:48
  • 5
    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. Oct 5, 2017 at 14:45
242

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
  • 7
    Yeah, but that would be much slower.
    – Mikel
    Feb 9, 2011 at 6:14
  • 24
    See stackoverflow.com/questions/3025162/… for better answers, e.g. scipy.comb or gmpy.comb.
    – Mikel
    Feb 9, 2011 at 6:16
  • 5
    For some definition of "slow". If computing poker odds it is perfectly acceptable. The OP didn't specify. Feb 9, 2011 at 6:28
  • 7
    @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?
    – DSM
    Mar 25, 2013 at 19:03
  • 4
    On my system it takes 10ms to compute 10000 C 500 and returns an answer of 861 digits. Accurate and not particularly "slow" :^) Mar 26, 2013 at 0:51

Not the answer you're looking for? Browse other questions tagged or ask your own question.