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

作者:罗兵 时间:2023-02-15 18:12:37 

本文实例讲述了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基于回溯法子集树模板解决选排问题示例

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

来源:http://www.cnblogs.com/hhh5460/p/6931710.html

标签:Python,回溯法
0
投稿

猜你喜欢

  • mybatis plus实体类中字段映射mysql中的json格式方式

    2024-01-22 16:11:37
  • php中如何判断一个网页请求是ajax请求还是普通请求

    2023-10-13 14:42:30
  • Django实现简单网页弹出警告代码

    2022-12-31 06:56:16
  • Oracle基本PLSQL的使用实例详解

    2024-01-21 11:17:41
  • 深入理解Pytorch中的torch. matmul()

    2023-06-03 05:29:18
  • 使用url_helper简化Python中Django框架的url配置教程

    2023-01-10 14:44:51
  • Java正则表达式API边界匹配

    2023-07-03 19:36:18
  • 一行Python代码制作动态二维码的实现

    2023-11-04 02:32:19
  • 详解pytest实现mark标记功能详细介绍

    2022-01-16 23:59:48
  • Python import与from import使用及区别介绍

    2022-05-17 12:09:19
  • Perl学习笔记之文件操作

    2022-04-01 21:48:18
  • Python3实现英文字母转换哥特式字体实例代码

    2023-08-04 10:28:11
  • 如果用JS得到字符串中出现次数最多的字母

    2007-12-03 21:01:00
  • python将一组数分成每3个一组的实例

    2021-11-21 01:40:35
  • Ubuntu 18.04.4安装mysql的过程详解 亲测可用

    2024-01-15 18:46:21
  • MySQL 移动数据目录后启动失败问题解决

    2024-01-23 02:45:42
  • Python使用定时调度任务的方式

    2021-03-10 01:40:24
  • jQuery事件的绑定、触发、及监听方法简单说明

    2024-02-24 12:50:53
  • Python使用StringIO和BytesIO读写内存数据

    2022-06-15 02:45:45
  • Golang 实现Redis 协议解析器的解决方案

    2024-02-19 20:09:36
  • asp之家 网络编程 m.aspxhome.com