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

Python基于回溯法子集樹模板解決數(shù)字組合問(wèn)題實(shí)例

 更新時(shí)間:2017年09月02日 12:32:52   作者:羅兵  
這篇文章主要介紹了Python基于回溯法子集樹模板解決數(shù)字組合問(wèn)題,簡(jiǎn)單描述了數(shù)字組合問(wèn)題并結(jié)合實(shí)例形式分析了Python回溯法子集樹模板解決數(shù)字組合問(wèn)題的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下

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

問(wèn)題

找出從自然數(shù)1、2、3、...、n中任取r個(gè)數(shù)的所有組合。

例如,n=5,r=3的所有組合為:

1,2,3
1,2,4
1,2,5
1,3,4
1,3,5
1,4,5
2,3,4
2,3,5
2,4,5
3,4,5

分析

換個(gè)角度,r=3的所有組合,相當(dāng)于元素個(gè)數(shù)為3的所有子集。因此,在遍歷子集樹的時(shí)候,對(duì)元素個(gè)數(shù)不為3的子樹剪枝即可。

注意,這里不妨使用固定長(zhǎng)度的解。

直接套用子集樹模板。

代碼

'''數(shù)字組合問(wèn)題'''
n = 5
r = 3
a = [1,2,3,4,5] # 五個(gè)數(shù)字
x = [0]*n # 一個(gè)解(n元0,1數(shù)組) 固定長(zhǎng)度
X = []  # 一組解
def conflict(k):
  global n, r, x
  if sum(x[:k+1]) > r: # 部分解的長(zhǎng)度超出r
    return True
  if sum(x[:k+1]) + (n-k-1) < r: # 部分解的長(zhǎng)度加上剩下長(zhǎng)度不夠r
    return True
  return False # 無(wú)沖突
# 套用子集樹模板
def comb(k): # 到達(dá)第k個(gè)元素
  global n, x, X
  if k >= n: # 超出最尾的元素
    #print(x)
    X.append(x[:]) # 保存(一個(gè)解)
  else:
    for i in [1, 0]: # 遍歷元素 a[k] 的兩種選擇狀態(tài):1-選擇,0-不選
      x[k] = i
      if not conflict(k): # 剪枝
        comb(k+1)
# 根據(jù)一個(gè)解x,構(gòu)造對(duì)應(yīng)的一個(gè)組合
def get_a_comb(x):
  global a
  return [y[0] for y in filter(lambda s:s[1]==1, zip(a, x))]
# 根據(jù)一組解X,構(gòu)造對(duì)應(yīng)的一組組合
def get_all_combs(X):
  return [get_a_comb(x) for x in X]
# 測(cè)試
comb(0)
print(X)
print(get_all_combs(X))

效果圖

更多關(guān)于Python相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進(jìn)階經(jīng)典教程

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。

相關(guān)文章

  • Python實(shí)現(xiàn)兩個(gè)list求交集,并集,差集的方法示例

    Python實(shí)現(xiàn)兩個(gè)list求交集,并集,差集的方法示例

    這篇文章主要介紹了Python實(shí)現(xiàn)兩個(gè)list求交集,并集,差集的方法,結(jié)合實(shí)例形式分析了Python使用intersection、union及difference方法實(shí)現(xiàn)兩個(gè)集合list的交集、并集與差集操作技巧,需要的朋友可以參考下
    2018-08-08
  • python遞歸&迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)

    python遞歸&迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn)

    這篇文章主要介紹了python遞歸&迭代方法實(shí)現(xiàn)鏈表反轉(zhuǎn),文章分享一段詳細(xì)實(shí)現(xiàn)代碼,需要的小伙伴可以參考一下,希望對(duì)你的學(xué)習(xí)或工作有所幫助
    2022-02-02
  • python中的selenium安裝的步驟(瀏覽器自動(dòng)化測(cè)試框架)

    python中的selenium安裝的步驟(瀏覽器自動(dòng)化測(cè)試框架)

    這篇文章主要介紹了python中的selenium安裝的步驟,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2020-03-03
  • python簡(jiǎn)單區(qū)塊鏈模擬詳解

    python簡(jiǎn)單區(qū)塊鏈模擬詳解

    這篇文章主要介紹了python簡(jiǎn)單區(qū)塊鏈模擬詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下
    2019-07-07
  • python executemany的使用及注意事項(xiàng)

    python executemany的使用及注意事項(xiàng)

    這篇文章主要介紹了python executemany的使用及注意事項(xiàng),非常不錯(cuò),具有參考借鑒價(jià)值,需要的朋友可以參考下
    2017-03-03
  • Python基礎(chǔ)之文件操作及光標(biāo)移動(dòng)詳解

    Python基礎(chǔ)之文件操作及光標(biāo)移動(dòng)詳解

    這篇文章主要為大家介紹了Python基礎(chǔ)之文件操作及光標(biāo)移動(dòng)詳解,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪
    2022-11-11
  • 詳解Python中open()函數(shù)指定文件打開方式的用法

    詳解Python中open()函數(shù)指定文件打開方式的用法

    well,我們這里所指的文件打開方式并不是指調(diào)用什么應(yīng)用程序去打開某個(gè)文件,而是只讀只寫或者二進(jìn)制等的打開方式,這里我們就來(lái)詳解Python中open()函數(shù)指定文件打開方式的用法
    2016-06-06
  • conda虛擬環(huán)境使用pip下載包到當(dāng)前環(huán)境的兩種方法

    conda虛擬環(huán)境使用pip下載包到當(dāng)前環(huán)境的兩種方法

    conda管理包很方便,但并不是所有包都有最新的conda版本,所以仍需要使用conda中的pip來(lái)安裝包,下面這篇文章主要給大家介紹了關(guān)于conda虛擬環(huán)境使用pip下載包到當(dāng)前環(huán)境的兩種方法,需要的朋友可以參考下
    2022-08-08
  • python實(shí)現(xiàn)單例的兩種方法解讀

    python實(shí)現(xiàn)單例的兩種方法解讀

    這篇文章主要介紹了python實(shí)現(xiàn)單例的兩種方法,具有很好的參考價(jià)值,希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方,望不吝賜教
    2023-03-03
  • Python如何讀寫CSV文件

    Python如何讀寫CSV文件

    這篇文章主要介紹了Python如何讀寫CSV文件,幫助大家更好的理解和學(xué)習(xí)python,感興趣的朋友可以了解下
    2020-08-08

最新評(píng)論