Python中有nCr函数吗？

Question

在Python的math库里，有没有像下面这个公式那样的内置nCr（从n中选r）的函数呢？

我知道这个计算可以自己编程实现，但在动手之前，我想先确认一下库里有没有现成的函数。

Answer 1

想要进行迭代操作吗？可以使用 itertools.combinations。常见用法如下：

>>> 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']

如果你只是想计算公式，可以用 math.factorial，不过对于大组合来说速度不太快。可以看看下面的 math.comb，这是在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

从Python 3.8开始，可以使用 math.comb，这个方法要快得多：

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

Answer 2

在Python 3.8及以上版本中，可以使用math.comb这个功能：

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

如果你使用的是旧版本的Python，可以用下面这个程序：

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