组合数学4-全排列与算法

文章目录

  • 全排列与算法
    • 一 钟声里的全排列
      • **思考**:生成算法
    • 二 字典序法
      • 1.递归
      • 2.字典序法
        • 例1:生成字母abc的全排列
        • 例2:生成123的全排列
        • 例3:生成839647521的全排列
      • 3.**思考**:局部连续变化
    • 三 SJT算法(Steinhaus–Johnson–Trotter algorithm)
      • 1. 引出思路
      • 2. 可移动数(mobile integer):
      • 3. SJT算法
    • 四 程序支持与STIRLING数
      • 1. 程序支持
      • 2. stirling数
      • 3.思考:更快更好的全排列生成算法?

全排列与算法

计算机权威参考书:Donald E.Knuth 《计算机程序设计艺术》

一 钟声里的全排列

16,17世纪在英国兴起以固定次序鸣响一套教堂钟楼(包括5-12个钟)的方法。每口钟由一人鸣响。其变化规定为数序,例如12345,21345,23145等。

quiz:三一教堂12口编钟的变换钟乐有多少不同的曲子?

P(12,12)

思考:生成算法

怎样生成这么多的全排列?

二 字典序法

全排列的生成算法就是从第一个排列开始逐个生成所有排列的方法。

1.递归

采用递归的思想:由{1,2,3n1}\{1,2,3\dots n-1\}的排列生成{1,2,3n}\{1,2,3\dots n\}的排列。如下图所示。
缺点:内存消耗大,时间复杂度高。

Smiley face
Smiley face

2.字典序法

每个排列的后继都可以从它的前驱经过最少的变化获得。

中心思想:保持尽可能共同前缀变化限制在尽可能后缀上。

例1:生成字母abc的全排列

abc的下一个序列是acb(后继比前驱大一点),acb的下一个序列是bac,bac的下一个序列是bca,bca的下一个序列是cab,cab的下一个序列是cba。如下图:

Smiley face

例2:生成123的全排列

如下图所示:

Smiley face

基本思想:123从右向左扫描,找到第一次下降的位置,3到2下降,则交换3,2,形成132,同理扫描132,3到1下降,找后缀中比当前位置大的最小数2和1交换,形成231,要保证后缀最小则需要3,1再次交换,得到213,依次类推得到从右向左扫描依次递增的序列321,得到所有全排列的结果。如下图所示

Smiley face

例3:生成839647521的全排列

产生839647521在字典序中的下一个排列是839651247,推理过程如下图所示。

Smiley face

3.思考:局部连续变化

通过字典序法,后缀变化较多,怎样通过微小变化得到下一个排列?

三 SJT算法(Steinhaus–Johnson–Trotter algorithm)

1. 引出思路

因为递归方法,每次产生新的排列总是局部的变化,三维空间来看轨迹连续,如下图所示:

Smiley face

从递归的思路出发,由{1,2,3}\{1,2,3\}全排列得到{1,2,3,4}\{1,2,3,4\}全排列,如下图

Smiley face

不难发现:

数字具有移动的方向
每次交换两个相邻的数字
最大的能移动的数字发生交换

2. 可移动数(mobile integer):

{1,2,3n}\{1,2,3\dots n\}每个数具有一定的移动方向
如果该数的方向指向的相邻数比该数小的话则称该数是可移动数
例如:263154按图中指向,可移动数为6 3 5.

Smiley face

3. SJT算法

思路:4按照箭头指向为最大可移动数,依次与3 2 1进行交换至最左端得到4 1 2 3,此时不可移动,按照指向3为最大可移动数,与2交换得到4 1 3 2,箭头指向改变,4重新变为最大可移动数,依次移动到最右端,得到1 3 2 4,以此类推,得到最终的全排列

Smiley face

四 程序支持与STIRLING数

1. 程序支持

java:

Smiley face
算法介绍:
Smiley face
学术界:
Smiley face

常用排列生成工具

#include \<algorithm>
bool next_permutation(iterator start,iterator end);
bool prev_permutation(iterator start,iterator end);

实际上一般情况下n!的数量级是非常可怕的。

2. stirling数

未使用n!n!的累乘的方法,而是用近似的解析方法能够近似的逼近n!n!

Smiley face
以60为例:
Smiley face

60个字符的全排列,按照计算机每秒生成10710^7个排列的计算机需要的时间是多少?
T=60!/(365×24×3600×107)=2.65×1067T=60!/(365×24×3600×10^7)=2.65×10^67年
所以,n!n!增长速度非常快。

3.思考:更快更好的全排列生成算法?

热门文章

暂无图片
编程学习 ·

Android 模拟器联网

先配置好adb环境变量,打开模拟器,cmd中输入adb shell 查看是否adb配置完成,exit退出adb模式,adb root将模拟器root,然后adb shell,可以直接setprop net.eth0.dns1 192.168.1.1 后面为自己ip地址
暂无图片
编程学习 ·

30 个纯 HTML5 实现的游戏

作者:Danny Markov 来源:tutorialzin 译者:前端小智浏览器和 JavaScript 的功能逐年不断的变强变大。曾几何时,任何类型的游戏都需要Flash。但随着 HTML5 发展,HTML5 + WebGL 游戏式就慢慢占领着这个舞台。以下是30款流行的游戏,它们可以在所有现代浏览器中运行,并且只使…
暂无图片
编程学习 ·

Python简介和安装

Python简介 Python是一种跨平台的计算机程序设计语言。是由荷兰著名的“龟叔(Guido van Rossum)在1989年圣诞节期间,为了打发无聊的圣诞节而编写的一个编程语言,是用龟叔喜欢看的一个马戏团来命名。在TIOBE排行榜中Python,C语言和JAVA一直位于前三甲,是非常流行的编程语言…
暂无图片
编程学习 ·

Unity学习(C#)——正则表达式

正则表达式:专门用于字符串处理的语言。 可以 解决: 1.检索:获取我们想要的部分 2.匹配:判断给定字符串是否符合正则表达式的过滤逻辑。即表述了字符串书写的规则。 定位元字符 $、^ (要用using System.Text.RegularExpressions;) $在结尾处插入 ^在开头处插入string s =…
暂无图片
编程学习 ·

Java工具类-使用RSA验签

1 私钥签名public static String signByKey(String content,String privateKey) {PKCS8EncodedKeySpec sp = new PKCS8EncodedKeySpec(new BASE64Decoder().decodeBuffer(privateKey));KeyFactory keyFactory = KeyFactory.getInstance("RSA");PrivateKey key = keyF…
暂无图片
编程学习 ·

Redis和Java客户端 Jedis

今日内容 1. redis1. 概念2. 下载安装3. 命令操作1. 数据结构4. 持久化操作5. 使用Java客户端操作redisRedis 1. 概念: redis是一款高性能的NOSQL系列的非关系型数据库1.1.什么是NOSQLNoSQL(NoSQL = Not Only SQL),意即“不仅仅是SQL”,是一项全新的数据库理念,泛指非关系型…
暂无图片
编程学习 ·

Hadoop(二)——HDFS的 I/O 流操作

API操作的HDFS系统都是框架封装好的,可以采用 I/O 流的方式实现数据的上传和下载。 HDFS文件上传 1、需求:将本地D盘上的honglou.txt文件上传到HDFS根目录 2、代码块@Test public void putFileToHDFS() throws IOException,InterruptedException,URISyntaxException{//1、获取…
暂无图片
编程学习 ·

Java实现文件浏览器下载

前言:先说下需求,项目需求是用户一点击一个前端页面的链接就可以下载一个压缩包.因为就1个文件,使用文件管理系统像fastDSF,阿里云的OSS这种没必要,直接放在nginx服务器上的怕不好管理,于是给我限定了把文件打包到部署时候的jar包中并实现浏览器下载. 废话不多说,直接上代码! 1…
暂无图片
编程学习 ·

视觉SLAM十四讲--1,2章

第一讲 前言 SLAM—simultaneous localization and mapping 同时定位与地图构建—它是指搭载特定传感器的主体,在没有环境先验信息的情况下,与运动过程中建立环境的模型,同时估计自己的运动。 课后题: 1、Ax=bAx=bAx=b 求解xxx 涉及到一个定理: 线性方程组有解的充分必要条…
暂无图片
编程学习 ·

当你忘记网站上的密码时怎么办?Python如何快速帮你找回?

前言本文的文字及图片来源于网络,仅供学习、交流使用,不具有任何商业用途,版权归原作者所有,如有问题请及时联系我们以作处理。现如今浏览器可谓是五花八门,火狐、UC、360、QQ 这些浏览器不论美观还是所谓的安全方面都做的很符合我们需求。但如果你的工作与 IT 挂钩,无疑 Chr…
暂无图片
编程学习 ·

C语言指针笔记

C语言指针 一.地址与指针变量 程序在执行过程中需要有内存来存储需要用到的数据和程序代码,它们都占据一些内存单元,地址是这些内存单元的编号,同时包括它所指向的数据的类型信息。因此,可以把地址形象化地称为"指针"。 但不要把地址和指针混为一个概念,地址是数…
暂无图片
编程学习 ·

ubuntu20.04微信无法输入中文解决

打开输入法首选项, 勾选show suggestion去微信聊天框输入你好,会提醒下一个字,将提醒的字按空格输入到聊天框,就可以输入中文了 缺点就是每次都要这么操作
暂无图片
编程学习 ·

zabbix 安装

文章目录zabbix 4.0 安装安装php7.2(也可以跳过这个依赖)安装mcrypt扩展安装仓库配置包安装 zabbix-server-mysql、zabbix-web-mysql 及zabbix-agent安装 zabbix-server-mysqlzabbix数据库创建创建数据库 zabbix添加zabbix账号导入数据:zabbix_server 配置修改启动zabbix_serve…
暂无图片
编程学习 ·

关于微服务架构最好的文章!

本文将介绍微服务架构和相关的组件,介绍他们是什么以及为什么要使用微服务架构和这些组件。本文侧重于简明地表达微服务架构的全局图景。❝ 为了防止不提供原网址的转载,特加上原文链接:https://www.cnblogs.com/skabyy/p/11396571.html要理解微服务,首先要先理解不是微服务…
暂无图片
编程学习 ·

知识图谱数据库《neo4j》安装与配置

一:安装步骤Neo4j是基于Java的图形数据库,运行Neo4j需要启动JVM进程,因此必须安装JAVA SE的JDK。1:liunx环境Neo4j下载地址:https://neo4j.com/download/other-releases/#releases(社区版免费)或者直接在服务器上使用命令下载:curl -O http://dist.neo4j.org/neo4j-commu…