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,尽管没有完善的元编程范式,一些天才的开发者还是创作了很多元编程