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

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

這篇文章主要給大家分享的是python回溯算法實(shí)現(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]]

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

先帖一個(gè)正確解法：

'''
回溯算法模板：
from: labuladong公眾號
result = []
def backtrack(選擇列表,路徑):
? ? if 滿足結(jié)束條件：
? ? ? ? result.add(路徑)
? ? ? ? return?
? ? for 選擇 in 選擇列表:
? ? ? ? 做選擇(要去重，判斷該選擇是否已經(jīng)在選擇列表中，已經(jīng)選過的不要選)
? ? ? ? backtrack(選擇列表,路徑)
? ? ? ? 選擇列表.removelast() #撤銷這個(gè)選擇，因?yàn)橐匦聫念^開始（回溯樹的跟節(jié)點(diǎn)）
'''
import copy
?
def backtrack(L,path):
?
? ? if len(path)==len(L):
? ? ? ? c = copy.copy(path) ?# 注意這里不是直接將path加到res中，而是深拷貝了一個(gè)對象
? ? ? ? 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)

此時(shí)的輸出：

這個(gè)結(jié)果著實(shí)令人疑惑，仔細(xì)分析后發(fā)現(xiàn)是python的淺拷貝搞的鬼。當(dāng)我們判斷l(xiāng)en(path) == L時(shí)，就將path append到res中，但事實(shí)上，res中存放的只是path的一個(gè)指針，當(dāng)我們對path進(jìn)行“撤銷選擇”時(shí)，即path.pop()，會連帶著將res中元素也修改掉，這顯然是不合理的。仔細(xì)看的話其實(shí)每一次輸出的第一列組合起來剛好是全排列。

再看一個(gè)錯(cuò)誤示例，在撤銷選擇時(shí)不適用path.pop()，而是path = path[:-1]。

import copy
?
def backtrack(L,path):
?
? ? if len(path)==len(L):
? ? ? ? c = copy.copy(path) ?# 注意這里不是直接將path加到res中，而是深拷貝了一個(gè)對象
? ? ? ? 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)

此時(shí)的輸出：

更加令人疑惑，使用debug調(diào)試后發(fā)現(xiàn)，path撤銷選擇，即path = path[:-1]沒起到作用，在向上回溯的過程中，由于函數(shù)簽名是

? ?backtrack(L,path)

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