字典序

在英文字典中，排列单词的顺序是先按照第一个字母以升序排列（即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 进制的数，这种情况下，所有排列的字典序等价于所有按照全排列顺序把数字写成的数集合的升序。