1.5.2字典序法
[例] 求839647521的下一个排列
找出比右边数字小的标号最大的数4
8397655 72124124517
44><＜2157
大小为于于后44的的缀用用橙绿色 色表 表示 示
在 找接后出上即缀其前87中后3缀59比2将861缀4344中此97大、变65找后52的1得5出为缀的标到比对翻7下号84换转一3大2最916个的大5。1数的24数77 5
1.5.2字典序法
对给定的字符集中的字符 规定了一个先后关系，在此基 础上规定两个全排列的先后是 从左到右逐个比较对应的字符 的先后。
1.5.2字典序法
[例]字符集{1,2,3},较小的数字较 先,这样按字典序生成的全排列是: 123,132,213,231,312,321。
※※ 一个全排列可看做一个字符串，字
规则：令n个元素为1，2,…,n. p p1 p2 pn 是 这n个数的任意一个排列，我们可以找到一 个序列和它对应，其中ai 可以看作是排列P中 数i+1所在位置右边比i+1小的数的个数。
例 排列3214，它是元素1，2，3，4的一个 排列, 它对应的序列是什么？
例 序列311对应的排列是什么？
练习
求839763ห้องสมุดไป่ตู้421的下一个排列
1.5.3邻位对换法
序数法和字典排序法，求下一个排列在 不进位的情况下很容易。这就启发我们， 能不能设计一种算法，下一个排列总是 上一个排列某相邻两位对换得到的。
活动状态
以1←2←3←4←为初始排列，箭头所指一侧，相邻 的数比它小时，则称该数组处在活动状态， 1 2 3←4←的←2←，3，4都处于的活动状态。
符串可有前缀、后缀。
1.5.2字典序法
生成给定全排列的下一个排列
所谓一个的下一个就是这一个与
下一个之间没有其他的。这就要 求这一个与下一个有尽可能长的 共同前缀，也即变化限制在尽可 能短的后缀上。
1.5.2字典序法
一般而言，设P是[1,n]的一个全排列。 P=P1P2…Pn=P1P2…Pj-1PjPj+1…Pk-1PkPk+1…Pn
算法步骤
（1）若P=P←1P←2…P→n 没有处于活动则结束 （2）将处于活动状态的各数中值最大者设
为m,则m和它的箭头所指一侧相邻的数互换 位置，而且比m大的所有数的箭头改变方向， 即 →改成←或←改成→，转向（1）。
求 ←8→3→9→64→7→5→2←1←下一个排列 求 ←9→3→8→64→7→5→2←1←下一个排列
I) j=max{i|Pi<Pi+1}, II) k=max{i|Pi>Pj} III) 对换Pj，Pk， IV) 将Pj+1…Pk-1PjPk+1…Pn翻转，
P’= P1P2…Pj-1PkPn…Pk+1PjPk-1…Pj+1即P的下一个
1.5.2字典序法
[例] 839647521是1--9的排列。1—9 的排列最前面的是123456789，最后面 的是987654321，从右向左扫描若都是 增的，就到了987654321，也就没有下 一个了。否则找出第一次出现下降的 位置。
1.5全排列的生成算法
全排列的生成算法 就是对于给 定的字符集，用有效的方法将所 有可能的全排列无重复无遗漏地 枚举出来。
1.5全排列的生成算法
这里介绍全排列算法三种：
(A)序数法 (B)字典序法 (C) 邻位对换法
1.5.1 序数法
自然数都可以用十进制表示方法表示出来，
例如小于 的1正0l 整数n可以用下列形式表示
也0就 a是i 说i, 可以证明从0到n!-1的n!个正整数
与
一一对 应
其中 (an1, an2 , , a2 , a1)
.
0 ai i,1 i n 1
1.5.1 序数法
例1 已知m=4000， 6! <4000<7!求m对应的 序列
1.5.1 序数法
把n-1个元素的序列 (an1, an2, , a2, a1) 和n个元 素的排列建立一一对应关系，从而得到一种 生成排列的算法－－序数法。
习题
5， 10 ，19 ， 22
出来
l 1
n ak10k k 0
0 ak 9
推广到p进制数，即
m
n ak pk k 0
0 ak p 1
例如计算机常常用二进制表示法
1.5.1 序数法
用1!, 2!, …,(n-1)!的组合表示小于n!的整数的方法。 可以证明：从0到n!-1的任何整数m可唯一的表示为
其中m an1(n 1)! an2 (n 2)! a2 2! a11!