字典序

字典序是指按照单词首字母顺序在字典中进行排序的方法。在数学中可推广到有序符号序列，可视为完全有序集合的元素序列的一种排序方法。

字典序有多种变体和推广。一种变体在考虑序列元素之前先比较序列的长度。另一种变体广泛用于组合学，通过为有限集指定全序来对子集进行排序，并将子集转换为应用字典序的递增序列。

字典序可以推广定义偏序集的笛卡尔积的顺序； 当且仅当笛卡尔积的所有因子都全序时，该顺序才是全序。

概念

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

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

形式定义

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

(a,b) ≤ (a′,b′) 当且仅当 a < a′ 或 (a = a′ 且 b ≤ b′).

结果是偏序。如果A和B是全序, 那么结果也是全序。^[1][2]

多个集合乘积的场合

上面的定义可以拓展：只要两个元素属于 A₁×A₂×...×A_n 这个笛卡尔积，或者可写成 X=(x₁, x₂, ..., x_n) 和 Y=(y₁, y₂, ..., y_n) 的有序多元组形式，那么两者即可排序——从前往后：

• 如果 x₁ 和 y₁ 没有顺序（按照 A₁上的偏序，下同）：那么 X 和 Y 没有顺序。
• 否则，如果 x₁ 在 y₁ 之前，那么 X 在 Y 之前；反之若 y₁ 在 x₁ 之前，那么 Y 在 X 之前。
• 否则 x₁ 和 y₁ 不分先后。接下来讨论 x₂ 和 y₂、x₃ 和 y₃等等。

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

对于英语单词来说，单词可以说是在笛卡尔积 A×A×A×... 这个集合上的多元组（其中集合 A 是二十六个英文字母的集合），那么在字典中排列单词的顺序就是这里说的字典序——这也就是“字典序”这个名称的由来。

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

参考文献

1. Egbert Harzheim. Ordered Sets. Springer. 2006: 88–89. ISBN 978-0-387-24222-4. 
2. Franz Baader; Tobias Nipkow. Term Rewriting and All That. Cambridge University Press. 1999: 18–19. ISBN 978-0-521-77920-3.