306

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.

Kyle F Hartzenberg
  • 2,567
  • 3
  • 6
  • 24
James Mertz
  • 8,459
  • 11
  • 60
  • 87

2 Answers2

378

The following program calculates nCr in an efficient manner (compared to calculating factorials etc.)

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

As of Python 3.8, binomial coefficients are available in the standard library as math.comb:

>>> from math import comb
>>> comb(10,3)
120
L3viathan
  • 26,748
  • 2
  • 58
  • 81
dheerosaur
  • 14,736
  • 6
  • 30
  • 31
  • 2
    Why comprehension not just xrange? – gorlum0 Feb 09 '11 at 07: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 01 '14 at 20:47
  • is it better to import operator than to use lambda x,y: x*y ? – Netzsooc Nov 14 '16 at 05:49
  • 1
    @Netzsooc: op.mul is approximately 25% faster in my quick timing test I did on my computer. YMMV. – Jake Griffin May 08 '17 at 06:26
  • 4
    seriously? There is no standard library that does this, like numpy etc? – Charlie Parker Sep 05 '17 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 '17 at 05: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. – combinatorist Oct 05 '17 at 14:45
  • 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). – combinatorist Oct 05 '17 at 14:55
  • why min(r, n - r)? – frostbite Apr 08 '18 at 15:47
  • 1
    @frostbite For performance. `ncr(n, r)` is equal to `ncr(n, n-r)` – dheerosaur Jun 22 '18 at 15:24
  • 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. – Haltarys Mar 09 '20 at 15:33
  • 1
    @Haltarys '/' is integer division in python 2, which is the first snippet written in. – Albert May 05 '20 at 16:00
  • 2
    Why did this have to wait till Python 3.8? O.o – matheburg Feb 21 '21 at 13:03
  • Any idea to do this for permutation? The denum part of this answer is great. – Muhammad Yasirroni Mar 28 '21 at 04:58
  • I would move the python 3.8 answer to the top, since that will be the best solution for most people from now on. – Alex Coventry Feb 01 '22 at 22:50
  • [`scipy.special.comb`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb) for older python versions – Trevor Boyd Smith Dec 15 '22 at 21:15
241

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

>>> import itertools
>>> itertools.combinations('abcd',2)
<itertools.combinations object at 0x01348F30>
>>> 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)

if __name__ == '__main__':
    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
Mark Tolonen
  • 166,664
  • 26
  • 169
  • 251
  • 7
    Yeah, but that would be much slower. – Mikel Feb 09 '11 at 06:14
  • 24
    See http://stackoverflow.com/questions/3025162/statistics-combinations-in-python for better answers, e.g. scipy.comb or gmpy.comb. – Mikel Feb 09 '11 at 06:16
  • 5
    For some definition of "slow". If computing poker odds it is perfectly acceptable. The OP didn't specify. – Mark Tolonen Feb 09 '11 at 06: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 '13 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" :^) – Mark Tolonen Mar 26 '13 at 00:51
  • 1
    @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). – CrazyCasta Jan 21 '16 at 23:28
  • @CrazyCasta You're completely right, I've deleted the comment. – Richard Fung Mar 18 '16 at 05:06
  • 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. – Tusk Jan 14 '19 at 17:14
  • [`scipy.special.comb`](https://docs.scipy.org/doc/scipy/reference/generated/scipy.special.comb.html#scipy.special.comb) for older python versions – Trevor Boyd Smith Dec 15 '22 at 21:15