字典序

数学概念

在数学中，字典或词典顺序（也称为词汇顺序，字典顺序，字母顺序或词典顺序）是基于字母顺序排列的单词按字母顺序排列的方法。这种泛化主要在于定义有序完全有序集合（通常称为字母表）的元素的序列（通常称为计算机科学中的单词）的总顺序。

简单理解

设想一本英语字典里的单词，何者在前何者在后？

显然的做法是先按照第一个字母、以 a、b、c……z 的顺序排列；如果第一个字母一样，那么比较第二个、第三个乃至后面的字母。如果比到最后两个单词不一样长（比如，sigh 和 sight），那么把短者排在前。

通过这种方法，我们可以给本来不相关的单词强行规定出一个顺序。“单词”可以看作是“字母”的字符串，而把这一点推而广之就可以认为是给对应位置元素所属集合分别相同的各个有序多元组规定顺序：下面用形式化的语言说明。

形式定义

给定两个偏序集A和B,(a,b)和(a′,b′)属于笛卡尔积A×B，则字典序定义为

结果是偏序。如果A和B是全序, 那么结果也是全序。

多个集合乘积

上面的定义可以拓展：只要两个元素属于 A×B×...×N 这个笛卡尔积，或曰可写成 T1=(a1, b1, ..., n1) 和 T2=(a2, b2, ..., n2) 的有序多元组形式，那么两者即可排序——从前往后：

T1 和 T2 甚至可以不一样长：只要对应位置的元素所属的集合相同（第一个位置的元素都属于 A 集合、第二个位置的元素都属于 B 集合、等等），即可套用上面的做法。如果比到后面发现两者之一的元素先耗尽了，那么可视情况规定短者排在前或在后。

回到英语单词的例子上来。单词可以说是在笛卡尔积 A×A×A×... 这个集合（其中集合 A 是二十六个英文字母的集合，注意组成笛卡尔积的这些集合不必彼此不同）上的多元组，那么在字典中排列单词的顺序就是这里说的字典序——这也就是“字典序”这个名称的由来。

举例来说，全排列{1,2,3} 按照字典序的下一个排列分别是 123、132、213、231、312 和 321。如果就数字集合 {1, 2, 3, ..., n} 的排列而言，这个集合的全排列本身可以看成是 n进制的数，这种情况下，所有排列的字典序等价于所有按照全排列顺序把数字写成的数集合的升序。

描述

字典序如下：

设P是1～n的一个全排列:p=p1p2......pn=p1p2......pj-1pjpj+1......pk-1pkpk+1......pn

1）从排列的右端开始，找出第一个比右边数字小的数字的序号j（j从左端开始计算），即 j=max{i|pi

2）在pj的右边的数字中，找出所有比pj大的数中最小的数字pk，即 k=max{i|pi>pj}（右边的数从右至左是递增的，因此k是所有大于pj的数字中序号最大者）

3）对换pj，pk

4）再将pj+1......pk-1pkpk+1......pn倒转得到排列p'=p1p2.....pj-1pjpn.....pk+1pkpk-1.....pj+1，这就是排列p的下一个排列。

程序源码

算法说明

设置了中介数的字典序全排列生成算法，与递归直接模拟法和循环直接模拟法的最大不同是，不需要模拟有序全排列的生成过程，也就不需要逐一地生成各个全排列，只要知道初始全排列，就能根据序号（m-1），直接得到第m个全排列，因此速度非常快。

它的缺点是在生成序号（m-1）的递增进进制数时，需要事先创建一个用来存储n的阶乘数n! 的数组p[]，所以n的值不能太大，否则就会溢出，根据我的测试结果，当1<=n<=20时不会溢出，当21<=n时会溢出。

设置了中介数的字典序全排列生成算法需要设置中介数，在实际应用中比较繁琐，不如由前一个排列直接推得下一个排列方便。