这里有新鲜出炉的Python入门,程序狗速度看过来!
Python 是一种面向对象、解释型计算机程序设计语言,由Guido van Rossum于1989年底发明,第一个公开发行版发行于1991年。Python语法简洁而清晰,具有丰富和强大的类库。它常被昵称为胶水语言,它能够把用其他语言制作的各种模块(尤其是C/C++)很轻松地联结在一起。
这篇文章主要介绍了Python基于回溯法子集树模板解决数字组合问题,简单描述了数字组合问题并结合实例形式分析了Python回溯法子集树模板解决数字组合问题的具体步骤与相关操作技巧,需要的朋友可以参考下
本文实例讲述了Python基于回溯法子集树模板解决数字组合问题。分享给大家供大家参考,具体如下:
问题
找出从自然数1、2、3、...、n中任取r个数的所有组合。
例如,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的所有组合,相当于元素个数为3的所有子集。因此,在遍历子集树的时候,对元素个数不为3的子树剪枝即可。
注意,这里不妨使用固定长度的解。
直接套用子集树模板。
代码
- '''数字组合问题'''
- n = 5
- r = 3
- a = [1,2,3,4,5] # 五个数字
- x = [0]*n # 一个解(n元0,1数组) 固定长度
- 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] 的两种选择状态:1-选择,0-不选
- x[k] = i
- if not conflict(k): # 剪枝
- comb(k+1)
- # 根据一个解x,构造对应的一个组合
- def get_a_comb(x):
- global a
- return [y[0] for y in filter(lambda s:s[1]==1, zip(a, x))]
- # 根据一组解X,构造对应的一组组合
- def get_all_combs(X):
- return [get_a_comb(x) for x in X]
- # 测试
- comb(0)
- print(X)
- print(get_all_combs(X))
效果图
希望本文所述对大家Python程序设计有所帮助。
来源: http://www.phperz.com/article/17/0911/345535.html