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
投稿猜你喜欢
- 昨天在写“同IP站点查询”工具的时候，需要先用ASP获取查询域名的IP，本来是用WSHSHELL组件，代码如下：<％@LANGUAGE
- 1.下载mysql的repo源$ wget http://repo.mysql.com/mysql-community-release-el
- Sybase于2008年11月4日在大中华区用户大会上宣布，联手神州数码金程（北京）科技有限公司对旗下领先的SQL Anywhere数据库进
可视化辅助函数在下面的代码的注释内有大致的操作基本操作与前面的人脸检测的操作相似，增加了可视化的辅助函数import matplotlib.- by yemoo有时在编写网页代码时发现，img底部莫名奇妙多出大约3px的空白，无论怎么调节css都不可以，今天再次遇到此问题，网上看了一
- 条件选取：torch.where(condition, x, y) → Tensor返回从 x 或 y 中选择元素的张量，取决于 condi
- model.pyimport datetimefrom django.contrib.auth.models import Userfrom
- 本文实例讲述了Joomla开启SEF的方法。分享给大家供大家参考，具体如下：使用SEF(search engine friendly)网址的
- 一般来说，通过c.Request.FormFile()获取文件的时候，所有内容都全部读到了内存。如果是个巨大的文件，则可能内存会爆掉；且，有
- Tebsorflow开源实现多GPU训练cifar10数据集：cifar10_multi_gpu_train.pyTensorflow开源实
- 经常为学校的各种刷分而发愁，得知开学无望，日后还要刷课，索性自动化一次，学而不用乃愚昧 聪慧四大模块初始化from selenium imp
- Oracle text是Oracle的全文检索技术，是9i版本标准版和企业版的一部分。Oracle text使用标准的sql语言索引、查找、
- 根据我们指定的条件检索函数中的元素import matplotlib.pyplot as pltimport numpy as npa =
- 本文实例讲述了Python实现根据日期获取当天凌晨时间戳的方法。分享给大家供大家参考，具体如下：# -*- coding:utf-8 -*-
- 本文实例讲述了Python延时操作实现方法。分享给大家供大家参考，具体如下：在日常的开发中，往往会遇到这样的需求，需要某一个函数在一段时间之
- 本文为大家分享了vue $emit 和 $on 组件通信，供大家参考，具体内容如下<!DOCTYPE html> <htm
- 使用conda安装requirement.txt的扩展包当你在GitHub上下载了代码时，可以看到有一个requirements.txt文件
- 最近在学习Golang语言，中间遇到一个前辈指点，有一个学习原则：Learning By Doing。跟我之前学习Java的经验高度契合。在
- Go语言基础三切片的定义1. 切片：切片是数组的一个引用，因此切片是引用类型。但自身是结构体，值拷贝传递。2. 切片的长度可以改变，因此，切
- Select字句在逻辑上是SQL语句最后进行处理的最后一步，所以，以下查询会发生错误：SELECT YEAR(OrderDate) AS O
