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

Python基于回溯法子集樹模板解決選排問題示例

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

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

問題

從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)??!

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

那么,套用子集樹模板即可。

代碼

'''
選排問題
從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]不能超過r
  if x[:k+1].count(x[k]) > r:
    return True
  return False # 無(wú)沖突
# 用子集樹模板實(shí)現(xià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]開始排列

效果圖

 

更多關(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)文章

  • numpy.delete刪除一列或多列的方法

    numpy.delete刪除一列或多列的方法

    下面小編就為大家分享一篇numpy.delete刪除一列或多列的方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧
    2018-04-04
  • Python 實(shí)現(xiàn)繪制子圖及子圖刻度的變換等問題

    Python 實(shí)現(xiàn)繪制子圖及子圖刻度的變換等問題

    這篇文章主要介紹了Python 實(shí)現(xiàn)繪制子圖及子圖刻度的變換等問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2021-05-05
  • 解決python 執(zhí)行sql語(yǔ)句時(shí)所傳參數(shù)含有單引號(hào)的問題

    解決python 執(zhí)行sql語(yǔ)句時(shí)所傳參數(shù)含有單引號(hào)的問題

    這篇文章主要介紹了解決python 執(zhí)行sql語(yǔ)句時(shí)所傳參數(shù)含有單引號(hào)的問題,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。一起跟隨小編過來(lái)看看吧
    2020-06-06
  • python35種繪圖函數(shù)詳細(xì)總結(jié)

    python35種繪圖函數(shù)詳細(xì)總結(jié)

    Python有許多用于繪圖的函數(shù)和庫(kù),比如Matplotlib,Plotly,Bokeh,Seaborn等,這只是一些常用的繪圖函數(shù)和庫(kù),Python還有其他繪圖工具,如Pandas、ggplot等,選擇適合你需求的庫(kù),可以根據(jù)你的數(shù)據(jù)類型、圖形需求和個(gè)人偏好來(lái)決定,本文給大家總結(jié)了python35種繪圖函數(shù)
    2023-08-08
  • python使用SMTP發(fā)送qq或sina郵件

    python使用SMTP發(fā)送qq或sina郵件

    這篇文章主要為大家詳細(xì)介紹了python使用SMTP發(fā)送qq或sina郵件,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2017-10-10
  • Windows系統(tǒng)下多版本pip的共存問題詳解

    Windows系統(tǒng)下多版本pip的共存問題詳解

    這篇文章主要給大家介紹了關(guān)于在Windows系統(tǒng)下多版本pip的共存問題,文中通過示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考借鑒,下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧。
    2017-10-10
  • Python如何給函數(shù)庫(kù)增加日志功能

    Python如何給函數(shù)庫(kù)增加日志功能

    這篇文章主要介紹了Python如何給函數(shù)庫(kù)增加日志功能,文中講解非常細(xì)致,代碼幫助大家更好的理解和學(xué)習(xí),感興趣的朋友可以了解下
    2020-08-08
  • 詳解python日期時(shí)間處理2

    詳解python日期時(shí)間處理2

    這篇文章主要為大家介紹了python日期時(shí)間處理,具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下,希望能夠給你帶來(lái)幫助
    2021-12-12
  • Python文件夾與文件的操作實(shí)現(xiàn)代碼

    Python文件夾與文件的操作實(shí)現(xiàn)代碼

    最近在寫的程序頻繁地與文件操作打交道,這塊比較弱,還好在百度上找到一篇不錯(cuò)的文章,這是原文傳送門,我對(duì)原文稍做了些改動(dòng)
    2014-07-07
  • Python Pandas實(shí)現(xiàn)DataFrame合并的圖文教程

    Python Pandas實(shí)現(xiàn)DataFrame合并的圖文教程

    我們?cè)谑褂胮andas處理數(shù)據(jù)的時(shí)候,往往會(huì)需要合并兩個(gè)或者多個(gè)DataFrame的操作,下面這篇文章主要給大家介紹了關(guān)于Pandas實(shí)現(xiàn)DataFrame合并的相關(guān)資料,需要的朋友可以參考下
    2022-07-07

最新評(píng)論