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

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

SJT算法在线视频

SJT算法

下一节:程序支持与Stirling公式

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

SJT算法课程教案、知识点、字幕

我们再回头看一下最开始

我们说到的递归的思路

其实我们会发现 递归的思路

虽然说有诸多这样的缺点

但是它有一个很好的特性

也就是说

它每次产生的新的排列总是局部的变化

如果我们把它能够放到一个三维空间上可以看到

它的轨迹是非常连续的

这是在我们算法中

实际上是一个非常好的特性

那么递归始终是具有

它不能攻破的一些缺陷的

我们如果能够设计一个非递归的方法

而且能够保证这样的邻域性的话

对我们来说是一个非常有效的方法

那么 我们来看一下是不是有这样一个方法呢

我们还是按照递归的思路来看

如果说我们已经有了123的全排列

那么 下面4来了

怎么去生成1234的所有的全排列呢

刚才我们看到在递归的思路中

会说最大的数字要从最右端向最左端

在两端之间来回往复

就可以生成新的全排列了

那么似乎每一个数字都有一个移动的方向

那我们从第一个序列开始看起

1234 这时候我们可以说4的方向是向左的

4的方向向左

依次向左 走到了最左端

走到了最左端之后

这时候它再也不能再往下走了

那么应该下一步该如何做呢

实际上

我们是要拿123这原有的基础排列进行变换

这时候我们该怎么换

我们自然也会找123中最大的那个数字

如果一开始我们认为

所有的数字都是向左边走的话

那这时候3可以和它相邻的2发生变换

变换之后

这时候4可以从左端再依次向右端去走

在我们这样一个思路里面 没有递归了

而仅仅引入了一些新的概念

包括每个数字应该有一定的方向

包括某些数字是可以通过和它的邻域进行交换的

因此呢我们给一个新的概念

叫做可移动数

英文叫做 Mobile integer

为什么称它是可移动数呢

我们首先对于一个序列12345

我们要给每一个数字具备一定的移动方向

什么样的数字才是可移动数呢

如果它箭头指向的是一个比它更小的数字的话

我们就称它为是可移动的

那么这样 举个例子

比如说有这样一个序列 263154

它的箭头方向分别是这样的

在这个序列里面谁是可移动的呢

我们会发现2指向的是6 自然数字比它大

它是不可移动的

而6指向3 它是可移动的

因此我们可以找到

依次找到所有的可移动数

那么有了可移动数的概念呢

我们就可以来看

什么样的数字具有可移动性

首先 我们想最小的数字1

最小的数字1 无论它朝左指还是朝右指

其他指向的数字肯定比它大

因此1在任何时候都是不可移动的

对于最大的一个数字呢

比如说在刚才序列中1234中

最大的是4

那么它始终是可以在两端进行移动的

只有当它到达两端

且它们方向指向这个端点的话

那么它是不可移动的

有了这个概念以后

我们就可以构造一个非递归的算法

首先 我们来以1234为例

在一开始的时候

我们把所有数字的方向全部指向左边

因为它是一个增序排列 在这个情况下

所有的数列都是可移动数

我们要移动的 是当前可移动数中

最大的一个

自然4是最大的一个可移动数 按照它的方向

它和它相邻的3进行交换

然后4再和它相邻的2进行交换 依次类推

直到当4达到左端的时候 我们会发现

4这时候的方向 指向了端点

那么它是不可移动的

到这个状态下

我们应该找当前最大的可移动数

此时4不可移动了 因此3可以移动

那么3再和它旁边的相邻数进行交换

这时候我们生成了一个新的数列

也就是4在这边

132 那下一步应该怎么样呢

我们实际上是希望 通过把3的交换

让4重新获得了可移动性

意味着任何一个数字当它交换之后

比它大的数字都应该换方向

所以有了这样一个思路

我们就可以设计出所有的全排列

依次根据最大的数字 最大的可移动数

从右到左 从左到右进行移动

而每次交换这个移动可移动数的时候呢

比它大的数字将会变换方向

依次类推后

直到最后一个序列所有的数字都不可移动了

我们的算法就可以结束了

这个算法呢实际上它的名字叫做steinhaus-johnson-trotter algorithm

大家就会觉得很奇怪

为什么好像有三个人的名字在这个算法里面

确实 实际上这个算法呢并不是一人独享

它是由三位数学家分别独立构造出来的

因此呢 我们可以简称这个算法是SJT算法

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

SJT算法笔记与讨论

也许你还感兴趣的课程:

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