Python基于回溯法子集树模板解决全排列问题示例
作者：罗兵 发布时间：2023-12-18 21:25:04
标签：Python,回溯法
本文实例讲述了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
0
投稿猜你喜欢
- 概述自己在用labelImg打好标签后，想只用其中几类训练，不想训练全部类别，又不想重新打标生成.xml文件，因此想到这个办法：直接在.xm
- #-*- coding: UTF-8 -*-'''Created on 2013-12-5@author: good
一、排序的基本概念和分类所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。排序算法，就是如何使得记录按- python3与python2的还是有诸多的不同，比如说在2中:print "Hello,World!" r
- $str=preg_replace("/\s+/", " ", $str); //过滤多余回车 $s
- 如下所示：import urllib.requestimport sysimport http.cookiejarimport urllib
- 一、自定义数据集现有数据如下：5个文件夹，每个文件夹是神奇宝贝的一种。每个图片形状、大小、格式不一。我们训练CNN的时候需要的是tensor
- 网上的SQL优化的文章实在是很多，说实在的，我也曾经到处找这样的文章，什么不要使用IN了，什么OR了，什么AND了，很多很多，还有很多人拿出
- 1、psutil是一个跨平台库（https://github.com/giampaolo/psutil）能够实现获取系统运行的进程和系统利用
- 本文实例讲述了Python实现获取照片拍摄日期并重命名的方法。分享给大家供大家参考，具体如下：python获取照片的拍摄日期并重命名。不支持
- 相关知识点：#key-value#字典是无序的，因为他没有下标，通过key找info={ 'stu01':"liu
- 快速排序的基本思想：首先选定一个数组中的一个初始值，将数组中比该值小的放在左边，比该值大的放在右边，然后分别对左边的数组进行如上的操作，对右
- 大家好，我是煎蛋哥！全国有很多彩民，其中购买最多的彩种分别是体彩大乐透和福彩双色球；虽然中大奖的概率极低，但是彩民纷至沓来，一方面抱着一份中
- 1.TCP是一种面向连接的可靠地协议，在一方发送数据之前，必须在双方之间建立一个连接，建立的过程需要经过三次握手，通信完成后要拆除连接，需要
- Ubuntu16.04自带python2.7与python3.5，某个项目编译却要求python版本大于等于3.7，遂考虑在原系统基础上再安
- 先上代码，主要语句为np.where(b[c]==1)，详细解释如下：import numpy as np b = np.array([[-
- 你的主页或者你管理的网站有各种密码需要保护，把密码直接放在数据库或者文件中存在不少安全隐患，所以密码加密后存储是最常见的做法。在ASP.NE
- Python是一种解释型、面向对象、动态数据类型的高级程序设计语言。Python由Guido van Rossum于 * 底发明，第一个
- 题目描述给定n个字符串，请对n个字符串按照字典序排列。输入描述:输入第一行为一个正整数n(1≤n≤1000),下面n行为n个字符串(字符串长
- 元编程，一个听起来特别酷的词，强大的Lisp在这方面是好手，对于Python，尽管没有完善的元编程范式，一些天才的开发者还是创作了很多元编程
