Python中是否有一个计算组合数的函数nCr？

Question

Python的math库中是否包含了类似下面展示的内置nCr（从n个元素中选择r个）函数？

我知道计算可以编程，但在开始之前，我想先确认一下是否内置了。

- James Mertz

---

https://dev59.com/JnI95IYBdhLWcg3w5ic4 - Mikel

您可以使用sympy.binomial函数，它可能会有所帮助。 - gorlum0

Scipy有一个用于此目的的函数： import scipy.misc，然后使用 scipy.misc.comb(N,k)。 - Aziz Alto

import scipy.misc scipy.special.comb(10,5)导入scipy.misc库 计算组合数C（10，5） - Shubham

如果您需要在循环中执行此操作，那么最好使用帕斯卡三角形。 - Tyler Heers

Answer 1

在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

- dheerosaur

---

分母可以使用阶乘进行计算，在Python 2中与Python 3相比较（随着r的增加略微慢一些？），而在Python 3中快得多。 - leewz

真的吗？没有像NumPy等标准库可以做到这一点吗？ - Charlie Parker

@CharlieParker，在许多环境中安装numpy并不容易。另外，为什么要为如此简单的问题费力气呢？ - dheerosaur

如果您想处理不可能的情况 (r < 0 或 r > n)，那么请在将 r 重置为最小值后添加语句 if r < 0: return 0。 - combinatorist

为什么这个要等到 Python 3.8 才能实现？O.o - matheburg

Answer 2

你想要迭代吗？使用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

- Mark Tolonen

---

可以，但是速度会慢很多。 - Mikel

请参见https://dev59.com/xHA75IYBdhLWcg3w790Y获取更好的答案，例如scipy.comb或gmpy.comb。 - Mikel

根据“缓慢”的某种定义，如果是计算扑克牌赔率，那么完全可以接受。但问题提出者没有指定。 - Mark Tolonen

@Renato：你在说什么？这个答案一点也不危险。你认为math.factorial返回浮点数而不是任意精度的整数吗？ - DSM

在我的系统上，计算10000 C 500需要10毫秒，并返回一个861位数字的准确且不特别“慢”的答案。 - Mark Tolonen