欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

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ì)分析請(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)

    本文主要介紹了python linecache讀取行更新的實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2023-03-03
  • Python3實(shí)現(xiàn)的騰訊微博自動(dòng)發(fā)帖小工具

    Python3實(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目錄下的文件

    這篇文章主要介紹了使用python實(shí)現(xiàn)正則匹配檢索遠(yuǎn)端FTP目錄下的文件的方法,非常的簡(jiǎn)單實(shí)用,需要的小伙伴參考下
    2015-03-03
  • libreoffice python 操作word及excel文檔的方法

    libreoffice python 操作word及excel文檔的方法

    這篇文章主要介紹了libreoffice python 操作word及excel文檔的方法,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2019-07-07
  • python之pyqt5通過按鈕改變Label的背景顏色方法

    python之pyqt5通過按鈕改變Label的背景顏色方法

    今天小編就為大家分享一篇python之pyqt5通過按鈕改變Label的背景顏色方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-06-06
  • python3實(shí)現(xiàn)繪制二維點(diǎn)圖

    python3實(shí)現(xiàn)繪制二維點(diǎn)圖

    今天小編就為大家分享一篇python3實(shí)現(xiàn)繪制二維點(diǎn)圖,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來看看吧
    2019-12-12
  • Python中利用Scipy包的SIFT方法進(jìn)行圖片識(shí)別的實(shí)例教程

    Python中利用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-06
  • PyTorch在Windows環(huán)境搭建的方法步驟

    PyTorch在Windows環(huán)境搭建的方法步驟

    這篇文章主要介紹了PyTorch在Windows環(huán)境搭建的方法步驟,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧
    2020-05-05
  • JupyterLab遠(yuǎn)程密碼訪問實(shí)現(xiàn)

    JupyterLab遠(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
  • Python?遺傳算法處理TSP問題詳解

    Python?遺傳算法處理TSP問題詳解

    遺傳算法(Genetic?Algorithm,?GA)是模擬達(dá)爾文生物進(jìn)化論的自然選擇和遺傳學(xué)機(jī)理的生物進(jìn)化過程的計(jì)算模型,是一種通過模擬自然進(jìn)化過程搜索最優(yōu)解的方法
    2022-11-11

最新評(píng)論