排列组合
百度百科:传送门
组合C(m,n)
组合,是指从m个字符中选取n个字符,获得所有的组合的数量统计。
一般代数运算是:C(m, n) = m!/n!(m-n)! m为下标,n为上标0!= 1速算方式是 C(m, n) = (m * (m-1) * ··· * (1+ m-n)) / n!例:C(5,3) = (5* 4* 3) / 3! = 10
首先是计算阶乘
def nn(n, j=0):'''j == 0 时,计算阶乘j != 0 时,计算 n * (n-1) * ··· * (1+j)'''a = 1for i in range(1+j, n+1):a = a * ireturn a
计算组合
def c(m, n):'''计算组合数Cmn,m为下标,n为上标'''a = nn(m, m-n)b = nn(n)# 因为n函数里的返回值 基数a = 1,且range计算值>=1# 所以无需考虑b==0return int(a / b)
结果
>>> print(c(5, 3))10>>> print(c(10, 1))10>>> print(c(10, 9))10>>>
排列A(m,n)
一般代数运算是:A(m, n) = m!/(m-n)! m为下标,n为上标0!= 1例:A(5,3) = 5! / (5-3)! = 60
def a1(m,n):'''A(m,n) = m!/(m-n)!'''return int(nn(m) / nn(m-n))
完整代码
import timeimport randomdef debug_get_func_runtime(func):def inner(*args, **kwargs):start = time.time()res = func(*args, **kwargs)end = time.time()print("function %s use time %s" % (func.__name__, (end - start)))return res, (end - start)return innerdic = []for j in range(10000):dic.append([random.randint(100, 200), random.randint(1,100)])def nn(n, j=0):'''j == 0 时,计算阶乘j != 0 时,计算 n * (n-1) * ··· * (1+j)'''a = 1for i in range(1+j,n+1):a = a * ireturn adef c1(m, n):'''计算组合数Cmn = '''return nn(m) / (nn(n) * nn(m-n))def c2(m, n):'''计算组合数Cmn'''a = nn(m, m-n)b = nn(n)return int(a / b)def a1(m,n):'''A(m,n) = m!/(m-n)!'''return int(nn(m) / nn(m-n))@debug_get_func_runtimedef test1():for k in dic:c1(k[0], k[1])@debug_get_func_runtimedef test2():for k in dic:c2(k[0], k[1])@debug_get_func_runtimedef test3():for k in dic:a1(k[0], k[1])test1()test2()test3()
结果function test1 use time 0.3269994258880615function test2 use time 0.12499642372131348function test3 use time 0.2750399112701416
那么问题来了,组合的速算方式 比 一般方法效率提升3倍。原因是少一次阶乘么?
/12/17 TBD