Python基于回溯法子集树模板解决选排问题示例
作者:罗兵 发布时间:2023-02-15 18:12:37
标签:Python,回溯法
本文实例讲述了Python基于回溯法子集树模板解决选排问题。分享给大家供大家参考,具体如下:
问题
从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。
如:从4个元素中挑选3个元素进行排列,每个元素最多可重复r次。
分析
解x的长度是固定的,为m。
对于解x,先排第0个位置的元素x[0],再排第1个位置的元素x[1]。我们把后者看作是前者的一种状态,即x[1]是x[0]的一种状态!!
一般地,把x[k]看作x[k-1]的状态空间a中的一种状态,我们要做的就是遍历a[k-1]的所有状态。
那么,套用子集树模板即可。
代码
'''
选排问题
从n个元素中挑选m个元素进行排列,每个元素最多可重复r次。其中m∈[2,n],r∈[1,m]。
作者:hhh5460
时间:2017年6月2日 09时05分
声明:此算法版权归hhh5460所有
'''
n = 4
a = ['a','b','c','d']
m = 3 # 从4个中挑3个
r = 2 # 每个元素最多可重复2
x = [0]*m # 一个解(m元0-1数组)
X = [] # 一组解
# 冲突检测
def conflict(k):
global n, r, x, X, a
# 部分解内的元素x[k]不能超过r
if x[:k+1].count(x[k]) > r:
return True
return False # 无冲突
# 用子集树模板实现选排问题
def perm(k): # 到达第k个元素
global n,m, a, x, X
if k == m: # 超出最尾的元素
print(x)
#X.append(x[:]) # 保存(一个解)
else:
for i in a: # 遍历x[k-1]的状态空间a,其它的事情交给剪枝函数!
x[k] = i
if not conflict(k): # 剪枝
perm(k+1)
# 测试
perm(0) # 从x[0]开始排列
效果图
希望本文所述对大家Python程序设计有所帮助。
来源:http://www.cnblogs.com/hhh5460/p/6931710.html
0
投稿
猜你喜欢
- 本文实例为大家分享了python控制nao机器人身体动作的具体代码,供大家参考,具体内容如下今天读的代码,顺便写了出来,与文档的对比,差不多
- 分析我们都知道一个可迭代对象可以通过iter()可以返回一个迭代器。如果想要一个对象称为可迭代对象,即可以使用for,那么必须实现__ite
- 我们知道分析MySQL语句查询性能的方法除了使用EXPLAIN 输出执行计划,还可以让MySQL记录下查询超过指定时间的语句,我们将超过指定
- 触发器是一种特殊的存储过程,触发器主要是通过事件进行触发而被自动调用执行,而存储过程必须通过存储过程的名称被调用。一、触发器的定义触发器是在
- 如下所示:import cv2import numpy as npbins = np.arange(256).reshape(256,1)d
- Div+CSS+JS组和能够实现很多好看的特殊的效果,这里推荐一款可刷新的下拉菜单:下面是js代码部分:<script type=te
- 在网上查了部分资料但是发现粘上去的代码都存在问题,无奈只好自己修改了一下,代码如下: 如下代码能正常运行,都是网上查找资料最后拼凑总结出来的
- 本文实例讲述了PHP实现的MD5结合RSA签名算法。分享给大家供大家参考,具体如下:<?phpclass Md5RSA{
- 一、先让飞机在屏幕上飞起来吧。(一)实现飞机类class Plane: def __init__(self,fil
- 如下所示:#!/usr/bin/env python#_*_ coding:utf-8 _*_name = ['hello'
- 一、节点的定义dom节点树图中可见节点HTML文档中的每个成分都是一个节点:整个文档是一个文档节点每个HTML标签是一个元素节点包含在HTM
- 在 MySQL 下,在进行中文模糊检索时,经常会返回一些与之不相关的记录,如查找 "%a%" 时,返回的可能有中文字符,
- 由于项目是thinkPHP做后端框架,一直以来都是多页面的后端路由,想使用火热的webpack有点无从下手(原谅我太菜,而且推广vue只有我
- 使用celery在django项目中实现异步发送短信在项目的目录下创建celery_tasks用于保存celery异步任务。在celery_
- 对于access数据库的日期时间类型字段存储的日期,直接从数据库中读出显示的效果是带时间的如,2009-06-13 18:00 ,如果只是希
- 方法一:巧用sum函数将list列表与一个空列表相加,就能把嵌套列表合并成一个a=[[1],[2],[3],[4],[5]]merge=su
- 需求:启动程序后,让用户输入工资,然后打印商品列表允许用户根据商品编号购买商品用户选择商品后,检测余额是否够,够就直接扣款,不够就提醒可随时
- 大家好,学完面向对象与异常处理机制之后,接下里我们要学习 包与模块 。首先我们要了解什么是包?什么是模块?接下来我们还要学习 如何自定义创建
- 一、问题的引入opencv在图像处理方面有着非常强大的功能,当我们需要使用opencv进行一些图像的矫正工作时,我们通常需要找到原图的一些关
- 大家觉得在接手遗留代码时,见到什么东东是最让人感到不耐烦的?复杂无比的 UML ?我觉得不是。我的答案是,超过两个 else 的 if ,或