当前课程知识点:组合数学 >  小乒乓球的组合之旅 >  钟声里的全排列 >  字典序法

返回《组合数学》慕课在线视频课程列表

字典序法在线视频

字典序法

下一节:SJT算法

返回《组合数学》慕课在线视频列表

字典序法课程教案、知识点、字幕

我想 大家做了刚才那道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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

字典序法笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。