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