python回溯演演算法實現全排列小練習分享

2022-02-21 13:05:43

問題：輸入列表L（不含重複元素），輸出L的全排列。

如輸入：L=[1,2,3]

則輸出：[[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

全排列問題，可以用回溯法解決，詳細分析請參考東哥公眾號：labuladong，看了之後醍醐灌頂。

先帖一個正確解法：

'''
回溯演演算法模板：
from: labuladong公眾號
result = []
def backtrack(選擇列表,路徑):
    if 滿足結束條件：
        result.add(路徑)
        return 
    for 選擇 in 選擇列表:
        做選擇(要去重，判斷該選擇是否已經在選擇列表中，已經選過的不要選)
        backtrack(選擇列表,路徑)
        選擇列表.removelast() #復原這個選擇，因為要重新從頭開始（回溯樹的跟節點）
'''
import copy
 
def backtrack(L,path):
 
    if len(path)==len(L):
        c = copy.copy(path)  # 注意這裡不是直接將path加到res中，而是深拷貝了一個物件
        res.append(c)
        # res.append(path)
        # print(res)
        return
    for i in L:
        if i in path:
            continue
        else:
            path.append(i)
            backtrack(L,path)
            #path = path[:-1]
            path.pop()  # 注意此處「復原」選擇的方法
 
if __name__ == '__main__':
    res = []
    L = [1,2,3]
    backtrack(L,[])
    print(res)

輸出：

以上演演算法使用python的深拷貝，假如不使用會怎樣呢？

看下面程式碼：

def backtrack(L,path):
 
    if len(path)==len(L):
        # c = copy.copy(path)  
        # res.append(c)
        res.append(path)
        print(res)
        return
    for i in L:
        if i in path:
            continue
        else:
            path.append(i)
            backtrack(L,path)
            #path = path[:-1]
            path.pop()  # 注意此處「復原」選擇的方法
 
if __name__ == '__main__':
    res = []
    L = [1,2,3]
    backtrack(L,[])
    print(res)

此時的輸出：

這個結果著實令人疑惑，仔細分析後發現是python的淺拷貝搞的鬼。當我們判斷len(path) == L時，就將path append到res中，但事實上，res中存放的只是path的一個指標，當我們對path進行“復原選擇”時，即path.pop()，會連帶著將res中元素也修改掉，這顯然是不合理的。仔細看的話其實每一次輸出的第一列組合起來剛好是全排列。

再看一個錯誤範例，在復原選擇時不適用path.pop()，而是path = path[:-1]。

import copy
 
def backtrack(L,path):
 
    if len(path)==len(L):
        c = copy.copy(path)  # 注意這裡不是直接將path加到res中，而是深拷貝了一個物件
        res.append(c)
        # res.append(path)
        print(res)
        return
    for i in L:
        if i in path:
            continue
        else:
            path.append(i)
            backtrack(L,path)
            path = path[:-1] # 換一種「復原」選擇的方法
            #path.pop()  # 注意此處「復原」選擇的方法
 
if __name__ == '__main__':
    res = []
    L = [1,2,3]
    backtrack(L,[])
    print(res)

此時的輸出：

更加令人疑惑，使用debug偵錯後發現，path復原選擇，即path = path[:-1]沒起到作用，在向上回溯的過程中，由於函數簽名是

   backtrack(L,path)

由於path是以一個引數的形式傳入函數的，所以每一層遞迴呼叫中，使用的path應該是同一個，當我們用path.pop()復原選擇時，每一層的遞迴棧中，path應該同時發生變化。（可以這麼類比，當我第一輪遞迴，path=[1,2,3]後，向上遞迴時，合理思考應該將path依次變成[1,2]、[1]，這樣才能繼續向裡面新增元素，組成不同的排列），但使用path = path[:-1]，偵錯發現除了本層遞迴棧以外，其他遞迴棧的path並未發生變化：

這次是深拷貝的鍋，我們合理懷疑path=path[:-1]，應該是生成了一個新的物件，即=左右的path並不是同一個物件，因此每層遞迴樹的path不會改變，來驗證一下：

到此這篇關於python回溯演演算法實現全排列小練習分享的文章就介紹到這了,更多相關python回溯演演算法實現全排列內容請搜尋it145.com以前的文章或繼續瀏覽下面的相關文章希望大家以後多多支援it145.com！

python回溯演演算法實現全排列小練習分享

熱門文章