1.5.1字典序法
求 839647521的下一个排列
7 5 2 1
4＜ 7<54>2>1
在后缀 7521中找出比 4大的数 7 5找出其中比 4大的最小数 5
5
4, 5 对换
8396 7 214
后缀变为 7421将此后缀翻转
12 4 7
接上前缀 83965得到 839651247
即 839647521的下一个。
[例 ]
为后缀大于 4的用 橙 色表示小于 4的用 绿 色表示
找出比右边数字小的第一个数 4
1.5.1字典序法
在 [1,n]的全排列中,n n-1 … 321
是最后一个排列,其中介数是 (n-1,
n-2,...,3,2,1)其序号为 n-1∑k× k!
k=1
另一方面可直接看出其序号为 n!-1
n-1 n-1
于是 n!-1= ∑k× k! 即 n!=∑k× k! +1
k=1 k=1
1.5.1字典序法
一般而言，设 P是 [1,n]的一个全排列。
P=P1P2…P n=P1P2…P j-1PjPj+1…P k-1PkPk+1…P n
j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}
对换 Pj,Pk,将 Pj+1…P k-1PjPk+1…P n翻转，
P’= P1P2…P j-1PkPn…P k+1PjPk-1…P j+1即 P的下
一个
1.5.1字典序法
2)计算给定排列的序号
839647521的序号即先于此排列的排列的个数。
将先于此排列的排列 按前缀分类 。
前缀先于 8的排列的个数,7× 8!第一位是 8,先于 83得的排列的个数,2× 7!前 2位是 83,先于 839得的排列的个数,6× 6!
先于此排列的的排列的个数：
7× 8! +2× 7!+6× 6!
前 3位是 839,先于 8396得的排列的个数,4× 5!
+4× 5!
前 4位是 8396 先于 83964得的排列的个数,2× 4!
+2× 4!
前 5位是 83964 先于 839647得的排列的个数,3× 3!
+3× 3!
前 6位是 839647 先于 8396475得的排列的个数,2× 2!
+2× 2!
前 7位是 8396475 先于 83964752得的排列的个数,1× 1!
+1× 1!
297191
前 8位固定，则最后一位也随之固定将 8!,7!,…,1! 前面的系数抽出，放在一起
得到 72642321
此数的特点：
7,8的右边 比 8小 的数的个数2,3的右边 比 3小 的数的个数6,9的右边 比 9小 的数的个数4,6的右边 比 6小 的数的个数,4的右边 比 4小 的数的个数3,7的右边 比 7小 的数的个数,5的右边 比 5小 的数的个数1,2的右边 比 2小 的数的个数
72642321是计算排列 839647521的序号的中间环节，
我们称之为 中介数 。
※ 这是一个很有用的概念。
1.5.1字典序法
一般而言,对于 [1,9]的全排列中介
数首位的取值为 0— 8，第 2位的取
值为 0— 7，以此类推，第 8位的取
值为 0,1。从而序号可表示为：
n-1∑ k
i(n-i)!
i=1
ki,Pi的右边比 Pi小的数的个数
i=1,2,…,n-1
1.5.1字典序法
由中介数推出排列的算法
[例 ] 由 72642321推算出 839647521
方法 1,P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _
P1=8
8
→7+1=82+1=3 → P2=3
3
6+1=7，但 3已在 P3左边出现，
↑
7+1=8，但 8已在 P3左边出现，
↑
8+1=9 → P3=9
9
4+1=5，但 已经在 P4左边出现，
5+1=6 → P4=6
6
，但 已经在 5左边出现，
3+1=4 =4
4
3+1=4，但 3,4已经在 P6左边出现，
4+1+1=6，但 6已经在 P6左边出现，
6+1=7 → P6=7
7
，但 已经在 7左边出现，
4，但 4已经在 P7左边出现，
4+1=5 7=5
5
1+1=2 → P8=2
→ P9=1
2 1
这个过程比较麻烦 (这酝酿着改进的可能 )，
该算法从左到右依次推出 P1,P2,…,P 9。
下述算法依次定出 1,2,3,…,9 的位置。
1.5.1字典序法
方法 2-1：
72642321中未出现 0,1在最右边中介数右端加一个 0扩成 9位，先定 1，每定一位，其左边未定位下加一点，从（位－
位下点数 =0）的位中选 最左 的。
7 2 6 4 2 3 2 1 0
定 1 的位置
1
● ● ● ● ● ● ● ●
2
2
● ● ● ● ● ● ● 3
3
● 4
4
● ● ● 5
5
● ● ● ●
6
6
● ●
7
7
● ●
8
8
9
9
由 72642321推算出 839647521
1.5.1字典序法
方法 2-2：
已定出上标‘ ● ’，找左起第一个 0，下标‘ __’
由 72642321推算出 839647521
●72642321-11111111=61531210
_ _ _ _ _ _ _ _ 12
● ● ● ●61531210 0 5042010
3
● ● ● ●
50420100 10000000=40420100
4
● ● ● ● ●
40420100 - 0 000 =3 31 00
5
● ● ● ● ● ● ● ●
30310100 2 200000
6
● ● ● ● ● ● ● ● ● ●
20200000 10100000=10100000
7
● ● ● ● ● ● ● ● ●● ● ●
10100000 -10100000= 0000000
8
● ● ● ●● ● ●00000000
9
以上两种从中介数求排列的算法都比较麻
烦。给定一排列与下一个排列各自的中介
数 →进位链（中介数的后继） →递增进位
制数
求 839647521的下一个排列
7 5 2 1
4＜ 7<54>2>1
在后缀 7521中找出比 4大的数 7 5找出其中比 4大的最小数 5
5
4, 5 对换
8396 7 214
后缀变为 7421将此后缀翻转
12 4 7
接上前缀 83965得到 839651247
即 839647521的下一个。
[例 ]
为后缀大于 4的用 橙 色表示小于 4的用 绿 色表示
找出比右边数字小的第一个数 4
1.5.1字典序法
在 [1,n]的全排列中,n n-1 … 321
是最后一个排列,其中介数是 (n-1,
n-2,...,3,2,1)其序号为 n-1∑k× k!
k=1
另一方面可直接看出其序号为 n!-1
n-1 n-1
于是 n!-1= ∑k× k! 即 n!=∑k× k! +1
k=1 k=1
1.5.1字典序法
一般而言，设 P是 [1,n]的一个全排列。
P=P1P2…P n=P1P2…P j-1PjPj+1…P k-1PkPk+1…P n
j=max{i|Pi<Pi+1},k=max{i|Pi>Pj}
对换 Pj,Pk,将 Pj+1…P k-1PjPk+1…P n翻转，
P’= P1P2…P j-1PkPn…P k+1PjPk-1…P j+1即 P的下
一个
1.5.1字典序法
2)计算给定排列的序号
839647521的序号即先于此排列的排列的个数。
将先于此排列的排列 按前缀分类 。
前缀先于 8的排列的个数,7× 8!第一位是 8,先于 83得的排列的个数,2× 7!前 2位是 83,先于 839得的排列的个数,6× 6!
先于此排列的的排列的个数：
7× 8! +2× 7!+6× 6!
前 3位是 839,先于 8396得的排列的个数,4× 5!
+4× 5!
前 4位是 8396 先于 83964得的排列的个数,2× 4!
+2× 4!
前 5位是 83964 先于 839647得的排列的个数,3× 3!
+3× 3!
前 6位是 839647 先于 8396475得的排列的个数,2× 2!
+2× 2!
前 7位是 8396475 先于 83964752得的排列的个数,1× 1!
+1× 1!
297191
前 8位固定，则最后一位也随之固定将 8!,7!,…,1! 前面的系数抽出，放在一起
得到 72642321
此数的特点：
7,8的右边 比 8小 的数的个数2,3的右边 比 3小 的数的个数6,9的右边 比 9小 的数的个数4,6的右边 比 6小 的数的个数,4的右边 比 4小 的数的个数3,7的右边 比 7小 的数的个数,5的右边 比 5小 的数的个数1,2的右边 比 2小 的数的个数
72642321是计算排列 839647521的序号的中间环节，
我们称之为 中介数 。
※ 这是一个很有用的概念。
1.5.1字典序法
一般而言,对于 [1,9]的全排列中介
数首位的取值为 0— 8，第 2位的取
值为 0— 7，以此类推，第 8位的取
值为 0,1。从而序号可表示为：
n-1∑ k
i(n-i)!
i=1
ki,Pi的右边比 Pi小的数的个数
i=1,2,…,n-1
1.5.1字典序法
由中介数推出排列的算法
[例 ] 由 72642321推算出 839647521
方法 1,P1 P2 P3 P4 P5 P6 P7 P8 P9_ _ _ _ _ _ _ _ _
P1=8
8
→7+1=82+1=3 → P2=3
3
6+1=7，但 3已在 P3左边出现，
↑
7+1=8，但 8已在 P3左边出现，
↑
8+1=9 → P3=9
9
4+1=5，但 已经在 P4左边出现，
5+1=6 → P4=6
6
，但 已经在 5左边出现，
3+1=4 =4
4
3+1=4，但 3,4已经在 P6左边出现，
4+1+1=6，但 6已经在 P6左边出现，
6+1=7 → P6=7
7
，但 已经在 7左边出现，
4，但 4已经在 P7左边出现，
4+1=5 7=5
5
1+1=2 → P8=2
→ P9=1
2 1
这个过程比较麻烦 (这酝酿着改进的可能 )，
该算法从左到右依次推出 P1,P2,…,P 9。
下述算法依次定出 1,2,3,…,9 的位置。
1.5.1字典序法
方法 2-1：
72642321中未出现 0,1在最右边中介数右端加一个 0扩成 9位，先定 1，每定一位，其左边未定位下加一点，从（位－
位下点数 =0）的位中选 最左 的。
7 2 6 4 2 3 2 1 0
定 1 的位置
1
● ● ● ● ● ● ● ●
2
2
● ● ● ● ● ● ● 3
3
● 4
4
● ● ● 5
5
● ● ● ●
6
6
● ●
7
7
● ●
8
8
9
9
由 72642321推算出 839647521
1.5.1字典序法
方法 2-2：
已定出上标‘ ● ’，找左起第一个 0，下标‘ __’
由 72642321推算出 839647521
●72642321-11111111=61531210
_ _ _ _ _ _ _ _ 12
● ● ● ●61531210 0 5042010
3
● ● ● ●
50420100 10000000=40420100
4
● ● ● ● ●
40420100 - 0 000 =3 31 00
5
● ● ● ● ● ● ● ●
30310100 2 200000
6
● ● ● ● ● ● ● ● ● ●
20200000 10100000=10100000
7
● ● ● ● ● ● ● ● ●● ● ●
10100000 -10100000= 0000000
8
● ● ● ●● ● ●00000000
9
以上两种从中介数求排列的算法都比较麻
烦。给定一排列与下一个排列各自的中介
数 →进位链（中介数的后继） →递增进位
制数
