排列组合
百度百科：传送门
组合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
