依教授的想法改用 python 的方法做出一樣的效果
n 個整數有 n! 種排列方式:
n = 3, n! = 3 * 2 = 6
六種排列如下:
0 1 2
0 2 1
1 0 2
1 2 0
2 0 1
2 1 0
以下我們來看一個特別的 "旋轉法" 的範例:
考慮 n = 4, n! = 24。
所有的 24 種排列，以及每一個動作詳細的說明如下：
設有一串列 data =[0, 1, 2, 3] 其元素值有以下的排列
0 1 2 3 ← 起始狀態，將 data[0] 移到最後產生下一個
1 2 3 0 ← 再將 data[0]移到最後產生下一個
2 3 0 1 ← 再將 data[0]移到最後產生下一個
3 0 1 2 ← 再將 data[0]移到最後產生下一個
0 1 2 3 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 2 3 1 ← 再將 data[0]移到最後產生下一個
2 3 1 0 ← 再將 data[0]移到最後產生下一個
3 1 0 2 ← 再將 data[0]移到最後產生下一個
1 0 2 3 ← 再將 data[0]移到最後產生下一個
0 2 3 1 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 3 1 2 ← 再將 data[0]移到最後產生下一個
3 1 2 0 ← 再將 data[0]移到最後產生下一個
1 2 0 3 ← 再將 data[0]移到最後產生下一個
2 0 3 1 ← 再將 data[0]移到最後產生下一個
0 3 1 2 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 1 2 3 ← 此時 1 也回到原來的位置
將 data[2] 移到最後產生新的排列
0 1 3 2 ← 再將 data[0]移到最後產生下一個
1 3 2 0 ← 再將 data[0]移到最後產生下一個
3 2 0 1 ← 再將 data[0]移到最後產生下一個
2 0 1 3 ← 再將 data[0]移到最後產生下一個
0 1 3 2 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 3 2 1 ← 再將 data[0]移到最後產生下一個
3 2 1 0 ← 再將 data[0]移到最後產生下一個
2 1 0 3 ← 再將 data[0]移到最後產生下一個
1 0 3 2 ← 再將 data[0]移到最後產生下一個
0 3 2 1 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 2 1 3 ← 再將 data[0]移到最後產生下一個
2 1 3 0 ← 再將 data[0]移到最後產生下一個
1 3 0 2 ← 再將 data[0]移到最後產生下一個
3 0 2 1 ← 再將 data[0]移到最後產生下一個
0 2 1 3 ← 此時 0 回到原來的位置
將 data[1] 移到最後產生新的排列
0 1 3 2 ← 此時 1 也回到原來的位置
將 data[2] 移到最後產生新的排列
0 1 2 3 ← 此時 2 也回到原來的位置
將 data[3] 移到最後產生新的排列
0 1 2 3 ← 此時 3 也回到原來的位置，全部都歸位結束輪替
def rot(data, n): # 將第n個搬到最後
val = data.pop(n)
data.append(val)
return data
def rot_n_chk(data, n): # 檢查第n個要不要搬
for i in range(n-1):
if data[i] == i:
rot(data, i+1)
else:
break
return data
def chk_stop(data, n): # 檢查所有的位置是否都歸位
res = 1
for i in range(n): # 只要第i位置對 chk=1, 位置不對 chk=0
chk=1 if data[i] == i else 0
res *= chk # 每位的乘積
return res # res乘積為1表示全歸位都輪完了
odata = [0, 1, 2, 3]
n = len(odata)
r= []
while True:
rot(odata, 0)
rot_n_chk(odata, n)
#print(num, odata)
b = odata[:]
r.append(b)
if chk_stop(odata, n):break
print(sorted(r))
沒有留言:
張貼留言