python使用回溯算法實現(xiàn)列表全排列

更新時間：2023年11月03日 09:30:06 作者：驚瑟

這篇文章主要介紹了python使用回溯算法實現(xiàn)列表全排列,研究的問題是輸入列表L（不含重復(fù)元素）,輸出L的全排列,全排列問題,可以用回溯法解決,需要的朋友可以參考下

python使用回溯算法實現(xiàn)列表全排列

問題：輸入列表L（不含重復(fù)元素），輸出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 滿足結(jié)束條件：
        result.add(路徑)
        return 
    for 選擇 in 選擇列表:
        做選擇(要去重，判斷該選擇是否已經(jīng)在選擇列表中，已經(jīng)選過的不要選)
        backtrack(選擇列表,路徑)
        選擇列表.removelast() #撤銷這個選擇，因為要重新從頭開始（回溯樹的跟節(jié)點）
'''
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)

此時的輸出：

這個結(jié)果著實令人疑惑，仔細分析后發(fā)現(xiàn)是python的淺拷貝搞的鬼。當(dāng)我們判斷l(xiāng)en(path) == L時，就將path append到res中，但事實上，res中存放的只是path的一個指針，當(dāng)我們對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調(diào)試后發(fā)現(xiàn)，path撤銷選擇，即path = path[:-1]沒起到作用，在向上回溯的過程中，由于函數(shù)簽名是

backtrack(L,path)

由于path是以一個參數(shù)的形式傳入函數(shù)的，所以每一層遞歸調(diào)用中，使用的path應(yīng)該是同一個，當(dāng)我們用path.pop()撤銷選擇時，每一層的遞歸棧中，path應(yīng)該同時發(fā)生變化。（可以這么類比，當(dāng)我第一輪遞歸，path=[1,2,3]后，向上遞歸時，合理思考應(yīng)該將path依次變成[1,2]、[1]，這樣才能繼續(xù)向里面添加元素，組成不同的排列），但使用path = path[:-1]，調(diào)試發(fā)現(xiàn)除了本層遞歸棧以外，其他遞歸棧的path并未發(fā)生變化：