Python基于回溯法子集树模板解决数字组合问题实例

作者:罗兵 时间:2022-12-18 15:57:26 

本文实例讲述了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基于回溯法子集树模板解决数字组合问题实例

希望本文所述对大家Python程序设计有所帮助。

来源:http://www.cnblogs.com/hhh5460/p/6920382.html

标签:Python,回溯法
0
投稿

猜你喜欢

  • 微信小程序如何调用图片接口API并居中显示

    2023-08-09 15:05:30
  • pandas创建新Dataframe并添加多行的实例

    2021-06-21 07:11:48
  • python PyAutoGUI 模拟鼠标键盘操作和截屏功能

    2022-11-12 08:16:41
  • ASP XML编程objXML.async = False

    2011-04-21 10:55:00
  • 基于TensorFlow的CNN实现Mnist手写数字识别

    2022-03-13 11:20:28
  • 用css和js实现firefox和IE支持局部打印

    2008-05-23 13:04:00
  • 基于python批量处理dat文件及科学计算方法详解

    2021-05-16 18:00:12
  • 拖拽翻页(ThrowPage)详解 cool

    2009-12-02 09:54:00
  • php中设置index.php文件为只读的方法

    2023-11-17 20:13:54
  • python fire库的使用实例教程

    2023-08-24 14:01:22
  • 用js实现小球的自由移动代码

    2023-08-23 02:57:29
  • 微信小程序实现富文本图片宽度自适应的方法

    2023-10-17 12:44:25
  • Python configparser模块应用过程解析

    2022-08-03 19:56:11
  • 如何使用Python的OpenCV库处理图像和视频

    2022-09-06 10:22:12
  • 在CMD命令行中运行python脚本的方法

    2023-08-03 18:54:38
  • 困惹的A标签

    2007-12-04 12:36:00
  • python实现简单倒计时功能

    2022-09-29 03:08:32
  • Python for循环搭配else常见问题解决

    2021-04-23 06:08:56
  • python列表和字符串的三种逆序遍历操作

    2022-09-09 03:00:56
  • 用JS访问操作iframe框架里的dom

    2008-11-10 13:05:00
  • asp之家 网络编程 m.aspxhome.com