263

Possible Duplicates:
Statistics: combinations in Python
counting combinations and permutations efficiently
Project euler problem in python (problem 53)

I'm looking to see if built in with the math library in python is the nCr (n Choose r) function:

enter image description here

I understand that this can be programmed but I thought that I'd check to see if it's already built in before I do.

Community
  • 1
  • 1
James Mertz
  • 7,901
  • 11
  • 59
  • 85

2 Answers2

329

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
  • 25,498
  • 2
  • 53
  • 71
dheerosaur
  • 13,801
  • 6
  • 29
  • 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
  • 4
    @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
229

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, use math.factorial:

import math

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

if __name__ == '__main__':
    print nCr(4,2)

In Python 3, use the integer division // instead of / to avoid overflows:

return f(n) // f(r) // f(n-r)

Output

6
Community
  • 1
  • 1
Mark Tolonen
  • 148,243
  • 22
  • 160
  • 229
  • 7
    Yeah, but that would be much slower. – Mikel Feb 09 '11 at 06:14
  • 22
    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