当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 钟声里的全排列 > 字典序法
我想 大家做了刚才那道quiz以后都会想
哇 十二个编钟
所有的全排列 那么多
到底该怎么把所有的排列都列出来呢
所以我们来仔细想一想
如何去生成所有的全排列
对于这个问题我们首先想
是不是可以拿最简单的例子来看
比如说只有一个元素
只有一个元素 自然就只有一个排列
那么如果有两个元素呢
比如说 我两个元素是1和2
这时候 我们发现
2相对于1来说 无非就是
要么在1的前面 要么在1的后面
有了这样的思想以后 我们再想
是不是可以通过两个元素的全排列去生成
三个元素的全排列呢
比如说 我们已经有了1 2 和 2 1
现在又来了一个3 对于3的位置
它可以针对两个元素的全排列
然后从最右边一直向左
依次挪动
就生成了一系列的三个元素的排列
同样 对于另外一个两个数的排列
比如说 2 1的话
那么3的位置可以从左边再依次向右
我们会发现 实际上通过一个比较短的排列
我们可以把最高位 进行挪位之后
生成一个比较长的排列
计算机系的同学肯定都了解 这种思想是什么呢
这就是递归的思想
它可以通过一个1到n-1个元素的全排列
去生成长度为n的全排列
但是我们都知道
递归有什么问题呢
虽然它的实现思想很简单
但是它的复杂度非常高
而且在实现中呢 它的内存消耗非常大
所以人们希望
有没有更直接的方法来求得所有的全排列呢
那么有没有我们很熟悉的一种全排列的方法呢
大家来看我手里拿的是什么
实际上就是一本英文字典呀
英文字典它就告诉了我们一种排列的方法
实际上我们称这种方法称为 字典序
那么从我们熟悉的字典给我们一些启示
我们可以按照某种顺序来依次排列
比如说我们就拿三个字母来看
abc 应该说这是最小的一个排列
那么abc之后是谁呢
我们只让它增加一点点 会发现我们要保证
前面的数字尽量不变
而后面呢 仅仅增大一点点
abc之后 a如果不动的话
怎么去增大后面的b和c呢
只要我们把b和c相互一交换
就产生了下一个序列
也就是 acb
那么acb的下一个是谁呢
我们仔细想一想
acb 如果a不变的话
后面的cb已经不可能再增大了
这时候我们怎么让这个序列变大一点点呢
我们需要把a增加一点
它和b进行了交换
然后之后
b后面的序列要保证 仅仅比刚才的大一点点
因此 后面的后缀部分需要尽可能的小
剩下的两个字母a和c它最小的排列就是ac
就是这三个字母的串
我们会发现 可以按照字典序给它一定的顺序
在我刚才的讲解中我们发现 要将一个串分为
前缀和后缀两个部分
在进行不断的字典序增序的过程中
我们要尽可能的保证
前序保证不变
而后序仅仅一步一步一步地逐渐增大
这就是字典序全排列生成算法的思想
有了这样的思想
其实我们不难把abc三个字母
所有对应的三阶乘的全部的排列依次列出来
为了清晰起见呢 我们不用字母来表示
我们用数字来分析一下全排列的生成算法
比如说我们就看三个数字 123
在123这所有六个的全排列里面
我们分析一下该如何去构造出来字典序法呢
字典序法的一个中心思想就是说
要在尽可能长的前缀前提下
去把后缀慢慢增加
那么我们来分析一下
123的全排列该如何生成呢
我们首先会想
既然我们要保证后缀尽可能的小
我们就应该从右往前去分析
它是否是一个最小的后缀
那么什么样情况下这个后缀
就再也不能再变大了呢
我们仔细分析
比如说123依次增加 123依次增加
直到最后一个序列
我们发现最后一个序列实际上
是321
那么如果从右端向左进行扫描
会发现
它的数字排序实际上是从右向左依次递增
这样的后缀它就不可能再增加了
有了这样一个想法我们就会想
那什么时候我们可以进行变化
把它变大一点点呢
如果一旦是从右向左扫描过程中发现
它不再是一个递增的爬坡过程
而变成向下的
那就意味着
这块我们是可以通过交换
把后缀变大一点点的
因此 我们的思路就是说
首先要保证 要从右向左进行扫描
扫描到第一次出现下降的位置
比如说在这里 123 我们从右向前扫描
会发现 2的位置已经出现下降了
那该怎么办呢
我可以让2稍微增大一点点
那么意味着2应该和后面比较大的数
进行交换
这样里面我们就将2和3进行交换
生成了一个新的排列
也就是132
那么132之后
再接着往下
132从右向左升降 所以我们会发现
在1的位置我们可以稍微地让它变化一下了
那么1应该和谁进行交换呢
是和3还是和2呢
当然都是比它大的
但是后面的要交换的对象
我们应该找一个偏小一点的
比如说在这里 如果我拿1和3交换的话
自然它的前缀变化太大了
这时候 我拿比1大的最小的那个数字
我们就会生成将132、1和2进行交换
变成了231
那么231是不是仅仅比132大那么一点点呢
我们会发现
实际上231的后缀
31部分并不是一个最小的后缀
只要我们把1 3一交换
又会生成一个更小的后缀 也就是213
到此我们发现
132的字典序列的下一个序列应该是213
依次 按照这样的思想 依次往复
我们就可以生成所有的字典序法
关键在哪呢
首先 我们要保证是从右向左进行扫描
找到第一次下降的位置
这个位置将要和后缀中
比当前位置大那么一点点
也就是比当前位置大的最小的数字进行交换
最后呢保证它的后缀是当前最小的后缀
就可以构成字典序法了
那下面呢
我们拿一个字符串
来看看怎么生成字典序下一个排列
下面呢我们用839647521给大家演示一下
字典序是怎么进行的
对于839647521来说它要找下一个排列
首先我们要从右到左
找第一次下降的位置
从右到左12574 当到达4的时候会发现
它由一个上升的趋势变成了下降
那么在这里我们就会发现
4这个数字是可以和它后面的数字进行交换
而逐步增大的
那么4要和谁进行交换呢
对于4后面有1257
肯定它要和比4大的数交换
同时我们不能和大的太多的数进行交换
因此我们必须找后缀中比4大的最小的那个数
这里 5比4大
而且也是后缀中比4大数中最小的一个
因此 7、5中 我们选择5
4和5进行交换之后
我们产生了一个新的数列
也就是 839657421
这时候 我们要保证后缀尽可能的小
7421 它本身是一个从右向左递增的后缀
显然 它是最大的后缀
因此 如果我们要让它最小的话
我们只需要将后缀 完全翻转
它就会变成从1247依次递增的
一个最小的后缀了
因此我们可以利用这三步规则
得到了839647521的下一个排列就是
839651247
通过刚才的计算我们知道了
839647521的下一个排列
在字典序中是839651247
对比这两个数字
我们会发现仅仅是序列中相邻的两个排列
但它们的变化却发生巨大的变化
这时候我们就会想
我们实际上希望
是不是通过一部分很小很小的微小变化
逐步递推 能够产生一个全排列呢
那么下面我们会介绍 另外一种方法
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验