Python基于回溯法子集樹模板解決數(shù)字組合問題實例
更新時間：2017年09月02日 12:32:52 作者：羅兵
這篇文章主要介紹了Python基于回溯法子集樹模板解決數(shù)字組合問題,簡單描述了數(shù)字組合問題并結(jié)合實例形式分析了Python回溯法子集樹模板解決數(shù)字組合問題的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下
本文實例講述了Python基于回溯法子集樹模板解決數(shù)字組合問題。分享給大家供大家參考，具體如下：
問題
找出從自然數(shù)1、2、3、...、n中任取r個數(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
分析
換個角度，r=3的所有組合，相當(dāng)于元素個數(shù)為3的所有子集。因此，在遍歷子集樹的時候，對元素個數(shù)不為3的子樹剪枝即可。
注意，這里不妨使用固定長度的解。
直接套用子集樹模板。
代碼
'''數(shù)字組合問題'''
n = 5
r = 3
a = [1,2,3,4,5] # 五個數(shù)字
x = [0]*n # 一個解（n元0,1數(shù)組） 固定長度
X = [] # 一組解
def conflict(k):
global n, r, x
if sum(x[:k+1]) > r: # 部分解的長度超出r
return True
if sum(x[:k+1]) + (n-k-1) < r: # 部分解的長度加上剩下長度不夠r
return True
return False # 無沖突
# 套用子集樹模板
def comb(k): # 到達第k個元素
global n, x, X
if k >= n: # 超出最尾的元素
#print(x)
X.append(x[:]) # 保存（一個解）
else:
for i in [1, 0]: # 遍歷元素 a[k] 的兩種選擇狀態(tài):1-選擇，0-不選
x[k] = i
if not conflict(k): # 剪枝
comb(k+1)
# 根據(jù)一個解x，構(gòu)造對應(yīng)的一個組合
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)造對應(yīng)的一組組合
def get_all_combs(X):
return [get_a_comb(x) for x in X]
# 測試
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īng)典教程》
希望本文所述對大家Python程序設(shè)計有所幫助。
相關(guān)文章
這篇文章主要介紹了Apache部署Django項目圖文詳解,文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07
Python數(shù)據(jù)可視化之Pyecharts使用詳解
Pyecharts是一個由百度開源的、用于生成Echarts圖表的類庫，可以用來進行數(shù)據(jù)可視化分析。本文將詳細講解一下Pyecharts的使用，需要的可以參考一下2022-04-04
這篇文章主要介紹了Pandas DataFrame求差集的示例代碼，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-12-12
當(dāng)你需要在Python中處理文本數(shù)據(jù)時,正則表達式絕對是你的瑞士軍刀,今天小編就來和大家一起聊聊Python中re模塊的那些實用技巧和常見陷阱吧2025-04-04
這篇文章主要介紹了Django url 路由匹配過程詳解，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2021-01-01
一些Centos Python 生產(chǎn)環(huán)境的部署命令(推薦)
這篇文章主要介紹了一些Centos Python 生產(chǎn)環(huán)境的部署命令，非常不錯，具有參考借鑒價值，需要的朋友參考下吧2018-05-05
python 深度學(xué)習(xí)中的4種激活函數(shù)
這篇文章主要介紹了python深度學(xué)習(xí)中的4種激活函數(shù),幫助大家更好的進行深度學(xué)習(xí)，感興趣的朋友可以了解下2020-09-09
這篇文章主要為大家詳細介紹了plotly分割顯示mnist的方法，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
這篇文章主要介紹了自己使用總結(jié)Python程序代碼片段,本文收集了如反向讀取文件、往文件中所有添加指定的前綴、匿名函數(shù)作為返回值、將二進制數(shù)轉(zhuǎn)為10進制數(shù)等實用代碼片段,需要的朋友可以參考下2015-06-06
ubuntu安裝sublime3并配置python3環(huán)境的方法
這篇文章主要介紹了ubuntu安裝sublime3并配置python3環(huán)境的方法，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-03-03