排列组合的计算方法

作者: gattonero | 来源:发表于2019-03-28 02:03 被阅读0次

排列组合的计算方法
MySQL的QPS、TPS的获取
功耗
科学计算方法和艺术计算方法
排列组合-js
数学
美乐家的几种减肥方案
阿迪达斯淘宝计算方法
排列组合
排列组合公式及排列组合算法

问题

求1,2,3...n的不同排列方式（n!）

思路

普通的排列问题，在python库中甚至有现成的库可以用来解决，我们这里考虑两种方案，首先是回溯的思路（递归）：
基于交换元素的回溯实现较为简单，每一次交换循环位置的元素和首元素，直到循环位置抵达末尾，交换完毕后回溯

当然也有其他的思路，比如使用一个mark数组记录当前去过的位置，然后每次找下一个没去过的位置，这种方法其实也属于回溯，比较容易理解其正确性

其次是非递归的实现，这里我还没有没有找到与递归等同效率的思路（目前时间复杂度要高出On），只能暂时记录下来留待之后改进了

这里主要思想是既然一共有n!个排列，那么n的排列相当于n-1的所有排列*n，得到n-1的所有排列后，其实只需在每种排列上加上1-n就行了

解决

# 递归
def rec(a, l, r):
    if l==r:
        print(*a)
        return
    for i in range(l, r+1):#注意这里下限是l，虽然把自己跟自己交换是一种重复，但这也是需要计算在内的
        a[i], a[l] = a[l], a[i]
        rec(a,l+1,r)
        a[i], a[l] = a[l], a[i]
rec([i+1 for i in range(n)], 0, n-1)

# 非递归
n = 4
t, steps = 1, [[1]]
while t < n:
    cur, t = [], t+1
    for i in range(1, t+1):
        for s in steps:
            cur.append([i, *[(i+x-1) % t+1 for x in s]])
    steps = cur
    print(*steps) #[1, 2, 3, 4] [1, 2, 4, 3] [1, 3, 4, 2] [1, 3, 2, 4] [1, 4, 2, 3] [1, 4, 3, 2] [2, 3, 4, 1] [2, 3, 1, 4]...

问题

求1-n中取出x个数字的方式（C(n,x)）

思路

同样考虑两种方式，首先是递归，记录当前位置和递归深度即可，递归深度为x即取数完毕

第二是非递归，这里运用了一点bit magic，大概意思是根据x二进制中最大递增后缀序列求出下一个排列，具体可以参见这篇文章

解决

# 递归
def comb(n,x,cur,start,depth,arr):
    if depth==x:
        arr.append(cur)
        return
    for next in range(start,n-x+depth+1):
        comb(n,x,cur+str(next),next+1,depth+1,arr)
comb(n,x,'',0,0,arr) # 01 02 03 04 12 13 14 23 24 34，这里下标是0开始的，不影响效果

# 非递归
n, x = 5, 3
start, end = (1 << c)-1, (1 << n) - (1 << (n-x)) # 这里start和end就是二进制中x个1在最开始和最末尾的数
v = start
while v <= end:
    # 这里结果所对应的二进制位为1的下标就是具体的组合
    print(bin(v)[2:].rjust(n, '0'))
    # 下面两行是求next permutation的位运算方法，具体解释可以参考引用的两篇资料
    t = (v | (v - 1)) + 1 
    w = t | ((int((t & -t) / (v & -v)) >> 1) - 1)
    v = w