python使用回溯算法實現(xiàn)列表全排列
python使用回溯算法實現(xiàn)列表全排列
問題：輸入列表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() #撤銷這個選擇，因為要重新從頭開始（回溯樹的跟節(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)此時的輸出：
這個結果著實令人疑惑， 仔細分析后發(fā)現(xiàn)是python的淺拷貝搞的鬼。當我們判斷l(xiāng)en(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調試后發(fā)現(xiàn)，path撤銷選擇，即path = path[:-1]沒起到作用，在向上回溯的過程中，由于函數(shù)簽名是
backtrack(L,path)
由于path是以一個參數(shù)的形式傳入函數(shù)的，所以每一層遞歸調用中，使用的path應該是同一個，當我們用path.pop()撤銷選擇時，每一層的遞歸棧中，path應該同時發(fā)生變化。（可以這么類比，當我第一輪遞歸，path=[1,2,3]后，向上遞歸時，合理思考應該將path依次變成[1,2]、[1]，這樣才能繼續(xù)向里面添加元素，組成不同的排列），但使用path = path[:-1]，調試發(fā)現(xiàn)除了本層遞歸棧以外，其他遞歸棧的path并未發(fā)生變化：
這次是深拷貝的鍋，我們合理懷疑path=path[:-1]，應該是生成了一個新的對象，即=左右的path并不是同一個對象，因此每層遞歸樹的path不會改變，來驗證一下：
破案了。
到此這篇關于python使用回溯算法實現(xiàn)列表全排列的文章就介紹到這了,更多相關python列表全排列內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
基于Mediapipe+Opencv實現(xiàn)手勢檢測功能
mediaPipe，他就是一個集成好的包括人臉關鍵位點識別、身體關鍵位點識別、手部關鍵位點識別的一個包或者庫，直接調用就能夠得到它的關鍵位點信息，本文給大家介紹Mediapipe+Opencv實現(xiàn)手勢檢測功能，感興趣的朋友一起看看吧2022-01-01
這篇文章主要介紹了Python爬取破解無線網絡密碼過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2019-09-09
這篇文章主要為大家詳細介紹了特征臉理論基礎之PCA主成分分析法，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-03-03
在日常辦公中,我們經常需要處理Excel文件,有時候需要將中文轉換為拼音縮寫以方便檢索和使用,下面我們就來看看如何使用Python實現(xiàn)這一功能吧2025-02-02
這篇文章主要介紹了python檢查序列seq是否含有aset中項的方法,涉及Python針對序列的相關判斷技巧,需要的朋友可以參考下2015-06-06
異常處理是編寫健壯可靠的?Python?代碼的一個基本方面,這篇文章為大家整理了Python中異常處理的5個最佳實踐,文中的示例代碼講解詳細,希望對大家有所幫助2024-01-01
python+pytest接口自動化之日志管理模塊loguru簡介
python中有一個用起來非常簡便的第三方日志管理模塊--loguru，不僅可以避免logging的繁瑣配置，而且可以很簡單地避免在logging中多進程多線程記錄日志時出現(xiàn)的問題，甚至還可以自定義控制臺輸出的日志顏色，接下來我們來學習怎么使用loguru模塊進行日志管理2022-05-05
這篇文章主要介紹了使用seaborn繪制強化學習中的圖片問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-01-01
python 時間 T 去掉 帶上ms 毫秒 時間格式的操作
這篇文章主要介紹了python 時間 T 去掉 帶上ms 毫秒 時間格式的操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2021-04-04
這篇文章主要介紹了keras做CNN的訓練誤差loss的下降操作，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-06-06