b038: 法老王的石獅子

小安一行人到埃及去探險，意外發現一座金字塔，透過當地學者翻譯石碑上的文字，得知只要將金字塔前幾隻大小不一的石獅子依照某種順序排列，金字塔的大門就會開啟，並且可以得到法老王的寶藏。不過由於這些石獅子的排列方式太多了，所以小安決定依照順序一個一個排列出來，你能幫他列出所有的排列方式嗎？

輸入說明：

輸入一個正整數 N (2<=N<=8)，代表有幾個石獅子要排列，而這些石獅子的編號從小到大為 1~N。

輸出說明：

請由小到大輸出所有的排列方式。

範例輸入：

2

範例輸出 ：

12
21

#===========================================
'''用子集樹實現全排列'''

# 衝突檢測：無
def conflict(k):
    global n, x, X, a
   
    return False # 無衝突
    
  
# 用子集樹範本實現全排列
def perm(k): # 到達第k個元素
    global n, a, x, X
    
    if k >= n:  # 超出最尾的元素
        print(x)
        #X.append(x[:]) # 保存（一個解）
    else:
        for i in set(a)-set(x[:k]): # 遍歷，剩下的未排的所有元素看作元素x[k-1]的狀態空間
            x[k] = i
            if not conflict(k): # 剪枝
                perm(k+1)


# 測試


print("輸入一個正整數 N (2<=N<=8)，代表有幾個石獅子要排列，而這些石獅子的編號從小到大為 1~N。")
print("輸入一個正整數 N (2<=N<=8) --> ")
n=int(input())

a=[]
for i in range (1 , n+1):
    a.append(i)
    
print (a)
print("\n\n")


x = [0]*n   # 一個解（n元0-1陣列）
X = []      # 一組解

perm(0)     # 從x[0]開始






===================== RESTART: F:/Python_APSC/b038-1.py =====================
輸入一個正整數 N (2<=N<=8)，代表有幾個石獅子要排列，而這些石獅子的編號從小到大為 1~N。
輸入一個正整數 N (2<=N<=8) --> 
4
[1, 2, 3, 4]



[1, 2, 3, 4]
[1, 2, 4, 3]
[1, 3, 2, 4]
[1, 3, 4, 2]
[1, 4, 2, 3]
[1, 4, 3, 2]
[2, 1, 3, 4]
[2, 1, 4, 3]
[2, 3, 1, 4]
[2, 3, 4, 1]
[2, 4, 1, 3]
[2, 4, 3, 1]
[3, 1, 2, 4]
[3, 1, 4, 2]
[3, 2, 1, 4]
[3, 2, 4, 1]
[3, 4, 1, 2]
[3, 4, 2, 1]
[4, 1, 2, 3]
[4, 1, 3, 2]
[4, 2, 1, 3]
[4, 2, 3, 1]
[4, 3, 1, 2]
[4, 3, 2, 1]
>>>