问题
求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
Ref
https://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/
http://blog.gaurav.im/2016/12/18/next-binary-permutation-bitwise-hackery/
https://graphics.stanford.edu/~seander/bithacks.html#NextBitPermutation
Tips
- x & -x是求x的二进制中最右边的1所对应位置的二进制数，比如x=01100100，x&-x=00000100，x为奇数这个值就一定是1
- x | x-1是将x的二进制中所有后继0置1，比如x=01100100，x&-x=01100111，同样x为奇数这个值就是本身
