python回溯算法實現(xiàn)全排列小練習(xí)分享

更新時間：2022年02月21日 11:16:23 作者：驚瑟

這篇文章主要給大家分享的是python回溯算法實現(xiàn)全排列小練習(xí)，文章根據(jù)例子：輸入列表L（不含重復(fù)元素），輸出L的全排列展開學(xué)習(xí)，需要的小伙伴可以參考一下

問題：輸入列表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ā)生變化：