Python基于回溯法子集樹模板解決全排列問題示例
更新時(shí)間：2017年09月07日 10:53:42 作者：羅兵
這篇文章主要介紹了Python基于回溯法子集樹模板解決全排列問題,簡單描述了全排列問題并結(jié)合實(shí)例形式分析了Python使用回溯法子集樹模板解決全排列問題的具體步驟與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下
本文實(shí)例講述了Python基于回溯法子集樹模板解決全排列問題。分享給大家供大家參考，具體如下：
問題
實(shí)現(xiàn) 'a', 'b', 'c', 'd' 四個(gè)元素的全排列。
分析
這個(gè)問題可以直接套用排列樹模板。
不過本文使用子集樹模板。分析如下：
一個(gè)解x就是n個(gè)元素的一種排列，顯然，解x的長度是固定的，n。
我們這樣考慮：對(duì)于解x，先排第0個(gè)元素x[0]，再排第1個(gè)元素x[1]，...，當(dāng)來到第k-1個(gè)元素x[k-1]時(shí)，就將剩下的未排的所有元素看作元素x[k-1]的狀態(tài)空間，遍歷之。
至此，套用子集樹模板即可。
代碼
'''用子集樹實(shí)現(xiàn)全排列'''
n = 4
a = ['a','b','c','d']
x = [0]*n # 一個(gè)解（n元0-1數(shù)組）
X = [] # 一組解
# 沖突檢測(cè)：無
def conflict(k):
global n, x, X, a
return False # 無沖突
# 用子集樹模板實(shí)現(xiàn)全排列
def perm(k): # 到達(dá)第k個(gè)元素
global n, a, x, X
if k >= n: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存（一個(gè)解）
else:
for i in set(a)-set(x[:k]): # 遍歷，剩下的未排的所有元素看作元素x[k-1]的狀態(tài)空間
x[k] = i
if not conflict(k): # 剪枝
perm(k+1)
# 測(cè)試
perm(0) # 從x[0]開始
效果圖
更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》
希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。
您可能感興趣的文章:
相關(guān)文章
這篇文章主要介紹了Python與Java間Socket通信實(shí)例代碼的相關(guān)資料,需要的朋友可以參考下2017-03-03
這篇文章主要介紹了python爬蟲beautifulsoup解析html方法，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
python 實(shí)現(xiàn)多維數(shù)組轉(zhuǎn)向量
今天小編就為大家分享一篇python 實(shí)現(xiàn)多維數(shù)組轉(zhuǎn)向量，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-11-11
keras分類之二分類實(shí)例(Cat and dog)
這篇文章主要介紹了keras分類之二分類實(shí)例(Cat and dog)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-07-07
Python matplotlib 動(dòng)畫繪制詳情
這篇文章主要介紹了Python matplotlib 動(dòng)畫繪制，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價(jià)值，感興趣的小伙伴可以參考一下2022-09-09
這篇文章主要介紹了Pycharm plot獨(dú)立窗口顯示的操作，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2020-12-12
Python控制臺(tái)實(shí)現(xiàn)交互式環(huán)境執(zhí)行
這篇文章主要介紹了Python程序如何在交互式環(huán)境中執(zhí)行,文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-06-06
這篇文章主要介紹了如何使用Python繪制世界疫情地圖，本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值,需要的朋友可以參考下2022-03-03
Python中三維坐標(biāo)空間繪制的實(shí)現(xiàn)
這篇文章主要介紹了Python中三維坐標(biāo)空間繪制的實(shí)現(xiàn)，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-09-09
這篇文章主要介紹了Python接單的過程記錄分享,需要的朋友可以參考下2021-04-04