快捷導(dǎo)航

Python基于回溯法子集樹(shù)模板解決選排問(wèn)題示例

更新時(shí)間：2017年09月07日 11:00:11 作者：羅兵

這篇文章主要介紹了Python基于回溯法子集樹(shù)模板解決選排問(wèn)題,簡(jiǎn)單描述了選排問(wèn)題并結(jié)合實(shí)例形式分析了Python使用回溯法子集樹(shù)模板解決選排問(wèn)題的具體實(shí)現(xiàn)步驟與相關(guān)操作注意事項(xiàng),需要的朋友可以參考下

本文實(shí)例講述了Python基于回溯法子集樹(shù)模板解決選排問(wèn)題。分享給大家供大家參考，具體如下：

問(wèn)題

從n個(gè)元素中挑選m個(gè)元素進(jìn)行排列，每個(gè)元素最多可重復(fù)r次。其中m∈[2,n]，r∈[1,m]。

如：從4個(gè)元素中挑選3個(gè)元素進(jìn)行排列，每個(gè)元素最多可重復(fù)r次。

分析

解x的長(zhǎng)度是固定的，為m。

對(duì)于解x，先排第0個(gè)位置的元素x[0]，再排第1個(gè)位置的元素x[1]。我們把后者看作是前者的一種狀態(tài)，即x[1]是x[0]的一種狀態(tài)?。?/p>

一般地，把x[k]看作x[k-1]的狀態(tài)空間a中的一種狀態(tài)，我們要做的就是遍歷a[k-1]的所有狀態(tài)。

那么，套用子集樹(shù)模板即可。

代碼

'''
選排問(wèn)題
從n個(gè)元素中挑選m個(gè)元素進(jìn)行排列，每個(gè)元素最多可重復(fù)r次。其中m∈[2,n]，r∈[1,m]。
作者：hhh5460
時(shí)間：2017年6月2日 09時(shí)05分
聲明：此算法版權(quán)歸hhh5460所有
'''
n = 4
a = ['a','b','c','d']
m = 3  # 從4個(gè)中挑3個(gè)
r = 2  # 每個(gè)元素最多可重復(fù)2
x = [0]*m  # 一個(gè)解（m元0-1數(shù)組）
X = []   # 一組解
# 沖突檢測(cè)
def conflict(k):
  global n, r, x, X, a
  # 部分解內(nèi)的元素x[k]不能超過(guò)r
  if x[:k+1].count(x[k]) > r:
    return True
  return False # 無(wú)沖突
# 用子集樹(shù)模板實(shí)現(xiàn)選排問(wèn)題
def perm(k): # 到達(dá)第k個(gè)元素
  global n,m, a, x, X
  if k == m: # 超出最尾的元素
    print(x)
    #X.append(x[:]) # 保存（一個(gè)解）
  else:
    for i in a: # 遍歷x[k-1]的狀態(tài)空間a，其它的事情交給剪枝函數(shù)！
      x[k] = i
      if not conflict(k): # 剪枝
        perm(k+1)
# 測(cè)試
perm(0) # 從x[0]開(kāi)始排列

效果圖

更多關(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獲取字符串中的email
這篇文章主要介紹了python獲取字符串中的email,通過(guò)調(diào)用re庫(kù)，通過(guò)使用compile、findall獲取字符串中的email，下文詳細(xì)實(shí)現(xiàn)過(guò)程需要的小伙伴可以參考一下
2022-03-03
Python?matplotlib?plotly繪制圖表詳解
plotly本身是個(gè)生態(tài)非常復(fù)雜的繪圖工具，它對(duì)很多編程語(yǔ)言提供接口。交互式和美觀易用應(yīng)該是?Plotly?最大的優(yōu)勢(shì)，而?Matplotlib?的特點(diǎn)則是可定制化程度高，但語(yǔ)法也相對(duì)難學(xué)，各有優(yōu)缺點(diǎn)。本文將通過(guò)示例詳細(xì)講解二者是如何繪制圖表的，需要的可以參考一下
2022-03-03
Python實(shí)現(xiàn)解析參數(shù)的三種方法詳解
這篇文章主要介紹了python解析參數(shù)的三種方法,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
2022-07-07
python新一代網(wǎng)絡(luò)請(qǐng)求庫(kù)之python-httpx庫(kù)操作指南
Python 的 httpx 包是一個(gè)用于 HTTP 交互的一個(gè)優(yōu)秀且靈活的模塊,下面這篇文章主要給大家介紹了關(guān)于python新一代網(wǎng)絡(luò)請(qǐng)求庫(kù)之python-httpx庫(kù)的相關(guān)資料,需要的朋友可以參考下
2022-09-09
使用python生成目錄樹(shù)
這篇文章主要為大家詳細(xì)介紹了使用python生成目錄樹(shù)、文件的程序，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下
2018-03-03
Python 內(nèi)置方法和屬性詳解
這篇文章主要為大家介紹了Python 內(nèi)置方法和屬性，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來(lái)幫助
2021-12-12
淺談Pandas Series 和 Numpy array中的相同點(diǎn)
今天小編就為大家分享一篇淺談Pandas Series 和 Numpy array中的相同點(diǎn)，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2019-06-06
python讀取raw binary圖片并提取統(tǒng)計(jì)信息的實(shí)例
今天小編就為大家分享一篇python讀取raw binary圖片并提取統(tǒng)計(jì)信息的實(shí)例，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過(guò)來(lái)看看吧
2020-01-01
python中map、any、all函數(shù)用法分析
這篇文章主要介紹了python中map、any、all函數(shù)用法,實(shí)例分析了map、any、all函數(shù)的相關(guān)使用技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下
2015-04-04
python 為什么說(shuō)eval要慎用
這篇文章主要介紹了python 為什么說(shuō)eval要慎用，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
2019-03-03