数学大学
钟声里的全排列
组合数学 · 小乒乓球的组合之旅
按 空格/→ 演示下一步
全部页面点击任意一页，跳回舞台从这页播放
数学大学
钟声里的全排列
组合数学 · 小乒乓球的组合之旅
字典序法
字典序法按「词典顺序」逐个生成排列：从最小排列开始，每次生成下一个。
下一个排列
从右找首个下降位，换以最小可行的大数，尾部升序反转
完备性
每步恰好前进一名，不重不漏
SJT算法
SJT 算法用相邻对换生成排列：每次只交换相邻两元素。
移动方向
每个元素带方向，指向更大的相邻者时为「活动」
相邻对换
每次交换最大活动元素与其方向所指邻居
程序支持与Stirling公式
程序生成排列可行，但 n! 增长恐怖：Stirling 公式给出量级估计。
程序枚举
递归或字典序法皆可批量生成
Stirling 公式
n! ≈ √(2πn)(n/e)^n，估枚举成本
本节要点
- ✓字典序法：从最小排列逐步求下一个
- ✓SJT：每次只交换相邻一对
- ✓Stirling 公式估算 n! 的量级
延伸主题：手推 4 个元素的字典序序列用 Stirling 估算 20!
课后思考
先自己回答，再展开参考答案——能讲出来才算真懂。
1字典序法求「下一个排列」的三个动作分别解决什么？
参考答案从右找首个下降位确定要增大的最高位；与该位右侧最小的大数交换，保证增幅最小；把交换位之后反转成升序，保证后缀最小。三者合起来恰好得到紧随其后的排列。
2为什么说 SJT 的相邻对换性质有价值？
参考答案相邻对换意味着相邻两个排列只差一处局部的微小变化，对需要「在上一解基础上微调」的应用（如生成排列的滑动验证）非常友好；纯字典序相邻排列可能整段重排。
3为什么说枚举法「笨但可靠」，如何与巧妙计数互补？
参考答案相邻对换意味着相邻两个排列只差一处局部微调，对需要「在上一解基础上微调」的应用（如滑动验证）很友好；纯字典序的相邻排列可能整段重排。