Mor*_*ock 114 python statistics combinations
我需要计算在Python combinatorials(NCR),但无法找到的功能做在math,numpy或stat 图书馆.类似于类型函数的东西:
comb = calculate_combinations(n, r)
我需要可能的组合数量,而不是实际的组合,所以itertools.combinations我不感兴趣.
最后,我想避免使用阶乘,因为我将计算组合的数字可能变得太大而且阶乘将变得非常可怕.
这似乎是一个非常容易回答的问题,但是我被淹没在关于生成所有实际组合的问题中,这不是我想要的.:)
非常感谢
Jou*_*nen 114
请参阅scipy.special.comb(旧版scipy中的scipy.misc.comb).当exact为False时,它使用gammaln函数来获得良好的精度而不需要花费太多时间.在确切的情况下,它返回一个任意精度的整数,这可能需要很长时间才能计算出来.
Nas*_*nov 112
为什么不自己写呢？这是一个单行或类似的:
from operator import mul # or mul=lambda x,y:x*y
from fractions import Fraction
def nCk(n,k):
return int( reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1) )
测试 - 打印Pascal的三角形:
>>> for n in range(17):
... print ' '.join('%5d'%nCk(n,k) for k in range(n+1)).center(100)
...
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1
>>>
PS.编辑以替换int(round(reduce(mul, (float(n-i)/(i+1) for i in range(k)), 1)))
,int(reduce(mul, (Fraction(n-i, i+1) for i in range(k)), 1))因此它不会错误的大N/K.
jfs*_*jfs 49
快速搜索谷歌代码给出(它使用来自@Mark Byers的答案的公式):
def choose(n, k):
"""
A fast way to calculate binomial coefficients by Andrew Dalke (contrib).
"""
if 0 <= k <= n:
ntok = 1
ktok = 1
for t in xrange(1, min(k, n - k) + 1):
ntok *= n
ktok *= t
n -= 1
return ntok // ktok
else:
return 0
choose()比scipy.misc.comb()你需要一个确切答案快10倍(在所有0 <=(n,k)<1e3对上测试).
def comb(N,k): # from scipy.comb(), but MODIFIED!
if (k > N) or (N < 0) or (k < 0):
return 0L
N,k = map(long,(N,k))
top = N
val = 1L
while (top > (N-k)):
val *= top
top -= 1
n = 1L
while (n < k+1L):
val /= n
n += 1
return val
Jim*_*son 28
如果您想要精确的结果,请使用sympy.binomial.这似乎是最快的方法,请放手.
x = 1000000
y = 234050
%timeit scipy.misc.comb(x, y, exact=True)
1 loops, best of 3: 1min 27s per loop
%timeit gmpy.comb(x, y)
1 loops, best of 3: 1.97 s per loop
%timeit int(sympy.binomial(x, y))
100000 loops, best of 3: 5.06 µs per loop
Tod*_*wen 21
在很多情况下,数学定义的字面翻译是相当充分的(记住Python会自动使用大数字算术):
from math import factorial
def calculate_combinations(n, r):
return factorial(n) // factorial(r) // factorial(n-r)
对于我测试的一些输入(例如,n = 1000 r = 500),这比reduce另一个(当前最高投票)答案中的一个线路快10倍以上.另一方面,它由@JF Sebastian提供的snippit表现出色.
Xav*_*hot 17
从 开始Python 3.8，标准库现在包含math.comb计算二项式系数的函数：
math.comb(n, k)
这是在不重复的情况下从 n 个项目中选择 k 个项目的方法数n! / (k! (n - k)!)：
import math
math.comb(10, 5) # 252
Wir*_*nto 10
这是另一种选择.这个最初是用C++编写的,因此它可以被反向移植到C++以获得有限精度的整数(例如__int64).优点是(1)它只涉及整数运算,(2)它通过连续的乘法和除法对避免膨胀整数值.我用Nas Banov的Pascal三角测试了结果,得到了正确的答案:
def choose(n,r):
"""Computes n! / (r! (n-r)!) exactly. Returns a python long int."""
assert n >= 0
assert 0 <= r <= n
c = 1L
denom = 1
for (num,denom) in zip(xrange(n,n-r,-1), xrange(1,r+1,1)):
c = (c * num) // denom
return c
基本原理:为了最小化乘法和除法的数量,我们将表达式重写为
n! n(n-1)...(n-r+1)
--------- = ----------------
r!(n-r)! r!
为了尽可能避免乘法溢出,我们将按照以下STRICT顺序从左到右进行评估:
n / 1 * (n-1) / 2 * (n-2) / 3 * ... * (n-r+1) / r
我们可以证明按此顺序操作的整数算术是精确的(即没有舍入误差).
小智 6
使用动态编程，时间复杂度为？（n * m），空间复杂度为？（m）：
def binomial(n, k):
""" (int, int) -> int
| c(n-1, k-1) + c(n-1, k), if 0 < k < n
c(n,k) = | 1 , if n = k
| 1 , if k = 0
Precondition: n > k
>>> binomial(9, 2)
36
"""
c = [0] * (n + 1)
c[0] = 1
for i in range(1, n + 1):
c[i] = 1
j = i - 1
while j > 0:
c[j] += c[j - 1]
j -= 1
return c[k]
您可以编写 2 个简单的函数，实际上它们比使用scipy.special.comb快 5-8 倍。事实上，您不需要导入任何额外的包，而且该函数很容易阅读。诀窍是使用记忆来存储先前计算的值，并使用nCr的定义
# create a memoization dictionary
memo = {}
def factorial(n):
"""
Calculate the factorial of an input using memoization
:param n: int
:rtype value: int
"""
if n in [1,0]:
return 1
if n in memo:
return memo[n]
value = n*factorial(n-1)
memo[n] = value
return value
def ncr(n, k):
"""
Choose k elements from a set of n elements - n must be larger than or equal to k
:param n: int
:param k: int
:rtype: int
"""
return factorial(n)/(factorial(k)*factorial(n-k))
如果我们比较时间
from scipy.special import comb
%timeit comb(100,48)
>>> 100000 loops, best of 3: 6.78 µs per loop
%timeit ncr(100,48)
>>> 1000000 loops, best of 3: 1.39 µs per loop
如果你的程序有一个上限n（比如n <= N）并且需要重复计算 nCr（最好是 >>N次），使用lru_cache可以给你一个巨大的性能提升：
from functools import lru_cache
@lru_cache(maxsize=None)
def nCr(n, r):
return 1 if r == 0 or r == n else nCr(n - 1, r - 1) + nCr(n - 1, r)
构建缓存（隐式完成）需要花费O(N^2)时间。任何后续调用都nCr将在 中返回O(1)。