Python基于回溯法子集树模板解决全排列问题示例
作者:罗兵 时间:2023-12-18 21:25:04
本文实例讲述了Python基于回溯法子集树模板解决全排列问题。分享给大家供大家参考,具体如下:
问题
实现 'a', 'b', 'c', 'd' 四个元素的全排列。
分析
这个问题可以直接套用排列树模板。
不过本文使用子集树模板。分析如下:
一个解x就是n个元素的一种排列,显然,解x的长度是固定的,n。
我们这样考虑:对于解x,先排第0个元素x[0],再排第1个元素x[1],...,当来到第k-1个元素x[k-1]时,就将剩下的未排的所有元素看作元素x[k-1]的状态空间,遍历之。
至此,套用子集树模板即可。
代码
'''用子集树实现全排列'''
n = 4
a = ['a','b','c','d']
x = [0]*n # 一个解(n元0-1数组)
X = [] # 一组解
# 冲突检测:无
def conflict(k):
global n, x, X, a
return False # 无冲突
# 用子集树模板实现全排列
def perm(k): # 到达第k个元素
global n, a, x, X
if k >= n: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存(一个解)
else:
for i in set(a)-set(x[:k]): # 遍历,剩下的未排的所有元素看作元素x[k-1]的状态空间
x[k] = i
if not conflict(k): # 剪枝
perm(k+1)
# 测试
perm(0) # 从x[0]开始
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6931585.html
标签:Python,回溯法
0
投稿
猜你喜欢
Python光学仿真学习衍射算法初步理解
2021-01-07 13:54:46
vue项目中全局引入1个.scss文件的问题解决
2024-05-29 22:44:38
解析go语言调用约定多返回值实现原理
2023-10-08 23:38:06
解决python3 中的np.load编码问题
2021-12-19 20:28:27
python语音识别指南终极版(有这一篇足矣)
2021-09-15 23:57:21
Mysql使用存储过程快速添加百万数据的示例代码
2024-01-19 21:51:26
Go语言net包RPC远程调用三种方式http与json-rpc及tcp
2024-05-29 22:06:14
python实现图像高斯金字塔的示例代码
2023-05-06 02:02:32
详解Python中for循环的使用
2023-06-13 13:55:40
MySQL Community Server 8.0.11安装配置方法图文教程
2024-01-26 06:02:45
python 批量修改 labelImg 生成的xml文件的方法
2022-09-03 12:04:23
python字典值排序并取出前n个key值的方法
2021-08-09 22:16:44
浅谈MySQL中的group by
2024-01-18 22:53:54
Python基于keras训练实现微笑识别的示例详解
2022-06-14 10:02:07
python笔记之mean()函数实现求取均值的功能代码
2022-01-12 07:06:47
MySQL笔记之触发器的应用
2024-01-18 17:23:32
python time模块时间戳 与 结构化时间详解
2021-04-09 11:06:42
Django在win10下的安装并创建工程
2021-10-12 18:54:57
asp.net 多数据库支持的思考
2024-01-16 04:50:45
详解Selenium 元素定位和WebDriver常用方法
2021-10-05 01:45:14