python回溯算法實(shí)現(xiàn)全排列小練習(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ì)分析請(qǐng)參考東哥公眾號(hào):labuladong,看了之后醍醐灌頂。
先帖一個(gè)正確解法:
''' 回溯算法模板: from: labuladong公眾號(hào) 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è)對(duì)象 ? ? ? ? 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
的深拷貝,假如不使用會(huì)怎樣呢?
看下面代碼:
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)我們對(duì)path進(jìn)行“撤銷選擇”時(shí),即path.pop()
,會(huì)連帶著將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è)對(duì)象 ? ? ? ? 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ā)生變化:
這次是深拷貝的鍋,我們合理懷疑path=path[:-1],應(yīng)該是生成了一個(gè)新的對(duì)象,即=左右的path并不是同一個(gè)對(duì)象,因此每層遞歸樹的path不會(huì)改變,來驗(yàn)證一下:
到此這篇關(guān)于python回溯算法實(shí)現(xiàn)全排列小練習(xí)分享的文章就介紹到這了,更多相關(guān)python回溯算法實(shí)現(xiàn)全排列內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
python linecache讀取行更新的實(shí)現(xiàn)
本文主要介紹了python linecache讀取行更新的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-03-03Python3實(shí)現(xiàn)的騰訊微博自動(dòng)發(fā)帖小工具
這篇文章主要為大家分享下騰訊微博自動(dòng)發(fā)帖的Python3代碼,需要的朋友可以參考下2013-11-11使用python實(shí)現(xiàn)正則匹配檢索遠(yuǎn)端FTP目錄下的文件
這篇文章主要介紹了使用python實(shí)現(xiàn)正則匹配檢索遠(yuǎn)端FTP目錄下的文件的方法,非常的簡(jiǎn)單實(shí)用,需要的小伙伴參考下2015-03-03libreoffice python 操作word及excel文檔的方法
這篇文章主要介紹了libreoffice python 操作word及excel文檔的方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2019-07-07python之pyqt5通過按鈕改變Label的背景顏色方法
今天小編就為大家分享一篇python之pyqt5通過按鈕改變Label的背景顏色方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-06-06python3實(shí)現(xiàn)繪制二維點(diǎn)圖
今天小編就為大家分享一篇python3實(shí)現(xiàn)繪制二維點(diǎn)圖,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12Python中利用Scipy包的SIFT方法進(jìn)行圖片識(shí)別的實(shí)例教程
SIFT算法可以檢測(cè)圖片中的局部特征,算法原理相當(dāng)復(fù)雜...但是!Python強(qiáng)大的第三方包Scipy中帶有實(shí)現(xiàn)SIFT算法的SIFT方法,我們只要拿來用就可以了,下面就為大家?guī)鞵ython中利用Scipy包的SIFT方法進(jìn)行圖片識(shí)別的實(shí)例教程.2016-06-06PyTorch在Windows環(huán)境搭建的方法步驟
這篇文章主要介紹了PyTorch在Windows環(huán)境搭建的方法步驟,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-05-05JupyterLab遠(yuǎn)程密碼訪問實(shí)現(xiàn)
本文主要介紹了JupyterLab遠(yuǎn)程密碼訪問實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-02-02