問題
求1,2,3...n的不同排列方式（n!）
思路
普通的排列問題铸史，在python庫中甚至有現(xiàn)成的庫可以用來解決缩膝，我們這里考慮兩種方案膜蠢，首先是回溯的思路（遞歸）：
基于交換元素的回溯實現(xiàn)較為簡單膜楷，每一次交換循環(huán)位置的元素和首元素砾嫉，直到循環(huán)位置抵達末尾抡砂，交換完畢后回溯
當(dāng)然也有其他的思路大咱，比如使用一個mark數(shù)組記錄當(dāng)前去過的位置，然后每次找下一個沒去過的位置注益，這種方法其實也屬于回溯碴巾，比較容易理解其正確性
其次是非遞歸的實現(xiàn)，這里我還沒有沒有找到與遞歸等同效率的思路（目前時間復(fù)雜度要高出On）丑搔，只能暫時記錄下來留待之后改進了
這里主要思想是既然一共有n!個排列厦瓢，那么n的排列相當(dāng)于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煮仇，雖然把自己跟自己交換是一種重復(fù)，但這也是需要計算在內(nèi)的
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個數(shù)字的方式（C(n,x)）
思路
同樣考慮兩種方式谎仲，首先是遞歸浙垫，記錄當(dāng)前位置和遞歸深度即可，遞歸深度為x即取數(shù)完畢
第二是非遞歸郑诺，這里運用了一點bit magic夹姥，大概意思是根據(jù)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辙诞，這里下標(biāo)是0開始的辙售，不影響效果
# 非遞歸
n, x = 5, 3
start, end = (1 << c)-1, (1 << n) - (1 << (n-x)) # 這里start和end就是二進制中x個1在最開始和最末尾的數(shù)
v = start
while v <= end:
# 這里結(jié)果所對應(yīng)的二進制位為1的下標(biāo)就是具體的組合
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所對應(yīng)位置的二進制數(shù)倘要，比如x=01100100圾亏，x&-x=00000100十拣，x為奇數(shù)這個值就一定是1
- x | x-1是將x的二進制中所有后繼0置1封拧，比如x=01100100，x&-x=01100111夭问，同樣x為奇數(shù)這個值就是本身
