日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

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

作者：驚瑟 ? 更新時間： 2022-04-25 編程語言

問題：輸入列表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不會改變，來驗證一下：

原文鏈接：https://blog.csdn.net/qq_34062683/article/details/121434653

欄目分類
最近更新