Python基于回溯法子集樹模板解決數(shù)字組合問題實例
本文實例講述了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的所有組合,相當于元素個數(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)造對應的一個組合 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)造對應的一組組合 def get_all_combs(X): return [get_a_comb(x) for x in X] # 測試 comb(0) print(X) print(get_all_combs(X))
效果圖
更多關于Python相關內(nèi)容感興趣的讀者可查看本站專題:《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》及《Python入門與進階經(jīng)典教程》
希望本文所述對大家Python程序設計有所幫助。
相關文章
Python實現(xiàn)兩個list求交集,并集,差集的方法示例
這篇文章主要介紹了Python實現(xiàn)兩個list求交集,并集,差集的方法,結(jié)合實例形式分析了Python使用intersection、union及difference方法實現(xiàn)兩個集合list的交集、并集與差集操作技巧,需要的朋友可以參考下2018-08-08python遞歸&迭代方法實現(xiàn)鏈表反轉(zhuǎn)
這篇文章主要介紹了python遞歸&迭代方法實現(xiàn)鏈表反轉(zhuǎn),文章分享一段詳細實現(xiàn)代碼,需要的小伙伴可以參考一下,希望對你的學習或工作有所幫助2022-02-02python中的selenium安裝的步驟(瀏覽器自動化測試框架)
這篇文章主要介紹了python中的selenium安裝的步驟,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧2020-03-03詳解Python中open()函數(shù)指定文件打開方式的用法
well,我們這里所指的文件打開方式并不是指調(diào)用什么應用程序去打開某個文件,而是只讀只寫或者二進制等的打開方式,這里我們就來詳解Python中open()函數(shù)指定文件打開方式的用法2016-06-06conda虛擬環(huán)境使用pip下載包到當前環(huán)境的兩種方法
conda管理包很方便,但并不是所有包都有最新的conda版本,所以仍需要使用conda中的pip來安裝包,下面這篇文章主要給大家介紹了關于conda虛擬環(huán)境使用pip下載包到當前環(huán)境的兩種方法,需要的朋友可以參考下2022-08-08