服务器之家

服务器之家 > 正文

Python基于回溯法子集树模板解决全排列问题示例

时间:2020-12-06 17:53     来源/作者:罗兵

本文实例讲述了Python基于回溯法子集树模板解决全排列问题。分享给大家供大家参考,具体如下:

问题

实现 'a', 'b', 'c', 'd' 四个元素的全排列。

分析

这个问题可以直接套用排列树模板。

不过本文使用子集树模板。分析如下:

一个解x就是n个元素的一种排列,显然,解x的长度是固定的,n。
我们这样考虑:对于解x,先排第0个元素x[0],再排第1个元素x[1],...,当来到第k-1个元素x[k-1]时,就将剩下的未排的所有元素看作元素x[k-1]的状态空间,遍历之。

至此,套用子集树模板即可。

代码

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
'''用子集树实现全排列'''
n = 4
a = ['a','b','c','d']
x = [0]*# 一个解(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基于回溯法子集树模板解决全排列问题示例

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

原文链接:http://www.cnblogs.com/hhh5460/p/6931585.html

相关文章

热门资讯

2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全
2020微信伤感网名听哭了 让对方看到心疼的伤感网名大全 2019-12-26
Intellij idea2020永久破解,亲测可用!!!
Intellij idea2020永久破解,亲测可用!!! 2020-07-29
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享
歪歪漫画vip账号共享2020_yy漫画免费账号密码共享 2020-04-07
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址
电视剧《琉璃》全集在线观看 琉璃美人煞1-59集免费观看地址 2020-08-12
最新idea2020注册码永久激活(激活到2100年)
最新idea2020注册码永久激活(激活到2100年) 2020-07-29
返回顶部