当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 钟声里的全排列 > 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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验