字典序

字典序可以描述为至少两个偏序集 X 和 Y 的笛卡尔积的顺序。我们也可以将字典序称为词典顺序、字母顺序和词典学顺序。字典序用符号 < 表示。我们可以在许多类别中使用字典序，具体描述如下：

涉及两个集合的顺序

假设有两个偏序集 (X, <₁) 和 (Y, <₂)。我们将使用以下方式来表示笛卡尔积 X * Y 上的字典序 <：

(x, y) < (z, d)

当且仅当

x <₁ z 或 (x = z 且 y <₂ d)。

涉及 N 个集合的顺序

我们还可以将上述定义的笛卡尔积推广到 n 个偏序集。为此，我们将假设偏序集 (X₁, <₁), (X₂, <₂), (X₃, <₃), …., (X_n, <_n)。我们将使用以下方式来表示笛卡尔积 X₁, X₂, X₃, ……, X_n 上的字典序 <：

(x₁, x₂, x₃, …., x_n) < (y₁, y₂, y₃, …., y_n),

或者它可能有一个整数 0 < i ≤ n，使得

x₁ = y₁, x₂ = y₂, x₃ = y₃,….., x_n-1 = y_n-1 且 a_i < b_i。

从上面的解释中，我们可以说，如果 X₁, X₂, X₃, ….., X_n 是偏序集，在这种情况下，字典序也将是偏序。同样，如果所有这些集合都有一个适当的排列（良序），在这种情况下，字典序将是全序。

词语排序

假设有一个由集合 X 表示的特定字母表。字母 x1, x2, x3, …., xk 的字母表 X 必须被假定为严格全序，如下所示：

x₁ < x₂ < x₃ < …. < x_k。

长度为 n 的字符串或单词将由第 n 个笛卡尔幂 Xⁿ 的元素表示。根据符号的顺序，我们可以确定两个单词的顺序。为此，我们将检查两个单词首次出现不同的位置，我们将从单词的开头开始检查。

如果存在两个长度不同的单词，那么我们将用尾随的空白字符填充较短的单词，以便较短的单词可以与最长的单词具有相同的长度。如果存在任何空白符号，那么它必须在字母表中的任何其他符号之前。通过这种方式，我们可以按字典序比较单词。

因此，借助基本的拉丁字母表，城市名称可以按以下方式排序：

为了比较不同长度的单词，我们还有另一个约定，它非常有用并经常用于比较，这个约定被称为短词序 (shortlex order)。在短词序过程中，最短的单词总是排在较长的单词之前。根据短词序，上述城市将按以下顺序排列：

数字元组的排序

假设 A = N。其中，集合 Nⁿ 用于表示 n 个自然数元组。例如：(2, 5, 8, 9) 对于 n = 4，或 (1, 4, 10, 15, 18, 20) 对于 n = 6。

字典序用于比较 n 个自然数元组。如果我们将它应用于自然数集合 N 上的小于顺序 <，那么我们可以按以下方式定义它：

(x₁, x₂, x₃, …, x_n) < (y₁, y₂, y₃, …., y_n),

这里 i ≤ n，使得对于所有 j < i，aj = bj 且 ai ≤ bi。

例如

(1, 1) < (1, 2) < (1, 3, 2) < (1, 3, 5); (7, 5, 4, 2) < (7, 6, 4, 2).

同样，我们可以使用其他数值对象的集合并在其上定义字典序。我们可以在 Rⁿ 上定义它，它用于包含 n 个实数元组，或者 Zⁿ，它用于包含 n 个整数元组。

子集的排序

如果有一些对象以列表的形式表示，并具有偏序，在这种情况下，我们可以使用字典序来对任何对象进行排序。这里我们需要对具有 n 个元素的集合 X 的子集进行排序。这些可以称为大小为 k 的子集或 X 的幂集的所有子集。

我们应该记住，在定义子集的排序时，子集内元素的顺序无关紧要。因此，根据隐含或给定的排序规则，我们首先将它们按升序排列。因此，借助标准的小于顺序，我们可以排列数字，并借助字母顺序，我们可以对字母进行排序。之后，我们能够将字典序应用于子集。

例如：在此示例中，我们有一个子集 X = {x, y, z, d}，我们将以以下方式显示其字典序：

Φ < {x} < {x, y} < {x, y, z} < {x, y, z, d} < {x, y, d} < {x, z} < {x, z, d} < {x, d} < {y} < {y, z} < {y, z, d} < {y, d} < {z} < {z, d} < {d}

自然语言中的字典序

字典序可以描述为按字母顺序排列单词、字符或数字。此顺序中的字母必须按 A 到 Z 排序。字典序也可以称为词典顺序。这是因为字典序的搜索与实际词典中特定单词的搜索相似。为此，我们将从包含以所需单词的第一个字母开头的单词的区域开始搜索。之后，我们将从该区域开始，并开始搜索包含所需单词的第二个字母的单词，此过程将继续。

现在我们通过一个例子来理解字典序，具体描述如下：

在这个例子开始时，我们有一个素数列表，即 {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}。当我们使用字典序排列这些素数时，列表将变为：{11, 13, 17, 19, 2, 23, 29, 3, 5, 7}。

现在我们将讨论另一个例子，以便我们能更深入地理解字典序。

在上面的例子中，有一个包含两个单词的列表，即 {educative, educated}。现在我们将使用字典序对这两个单词列表进行排序。为此，我们将逐字母比较这两个单词，然后我们将按字母顺序对这些字母进行排序。之后，我们将得到一个列表形式的结果，例如 {educated, educative}。

字典序的例子

字典序包含许多例子，其中一些描述如下：

例 1：在此例中，我们必须使用具有小于关系的字典序，并且我们必须借助此顺序定义笛卡尔平方 A²，其中 A = {1, 2, 3, 4}。这里我们必须确定 A² 中所有大于 (3, 2) 的对。

解：A² 上的字典序将表示如下：

(1, 1) < (1, 2) < (1, 3) < (1, 4) < (2, 1) < (2, 2) < (2, 3) < (2, 4) < (3, 1) < (3, 2) < (3, 3) < (3, 4) < (4, 1) < (4, 2) < (4, 3) < (4, 4).

现在从上面的对中，我们将选择那些大于 (3, 2) 的对，具体描述如下：

(3, 3), (3, 4), (4, 1), (4, 2), (4, 3), (4, 4)

例 2：在此例中，我们必须使用具有小于关系的字典序，并且我们必须借助此顺序定义笛卡尔平方 B³，其中 B = {1, 2, 3}。这里我们必须确定 B³ 中所有大于 (2, 1, 3) 且小于 (3, 2, 1) 的元素。

解：B³ 元素列表上的字典序将表示如下：

(1, 1, 1) < (1, 1, 2) < (1, 1, 3) < (1, 2, 1) < …. < (3, 2, 3) < (3, 3, 1) < (3, 3, 2) < (3, 3, 3)

现在从上面的对中，我们将选择那些大于 (2, 1, 3) 且小于 (3, 2, 1) 的对，具体描述如下：

(2, 2, 1), (2, 2, 2), (2, 2, 3), (2, 3, 1), (2, 3, 2), (2, 3, 3), (3, 1, 1), (3, 1, 2), (3, 1, 3)

例 3：在此例中，我们有一个集合 {x, y, z, u, v} 的所有 3 个子集的列表，我们必须按字典序排列它们。

解：集合 {x, y, z, u, v} 的所有 3 个子集列表上的字典序将表示如下：

{x, y, z} < {x, y, u} < {x, y, v} < {x, z, u} < {x, z, v} < {x, u, v} < {y, z, u} < {y, z, v} < {y, u, v} < {z, u, v}。

例 4：在此例中，我们有一个集合 {1, 2, 3, 4, 5, 6} 的所有 4 个子集的列表，我们必须按字典序排列它们。

解：集合 {1, 2, 3, 4, 5, 6} 的所有 4 个子集列表上的字典序将表示如下：

{1, 2, 3, 4} < {1, 2, 3, 5} < {1, 2, 3, 6} < {1, 3, 4, 5} < {1, 3, 4, 6} < {1, 4, 5, 6} < {2, 3, 4, 5} < {2, 3, 4, 6} < {2, 4, 5, 6} < {3, 4, 5, 6}.

例 5：在此例中，有两个偏序集 (A, ≤) 和 P(A)，其中 A = {1, 2, 3}，P(A) 用于表示 A 的幂集。这里我们有一个具有小于关系 (<) 的字典序，它定义在笛卡尔积 A * P(A) 上。现在我们必须找出以下语句是真还是假。

1. (2, φ) < (1, {1, 2, 3})
2. (1, {1}) < (2, {2, 3})
3. (2, {1}) < (2, {2, 3})
4. (3, {1, 3}) < (3, {2, 3})
5. (3, {1, 3}) < (3, {1, 2, 3})

解决方案

1. 第一个语句 (2, φ) < (1, {1, 2, 3}) 包含条件 2。因此，这个语句是假的。
2. 第二个语句 (1, {1}) < (2, {2, 3}) 包含条件 1 ≤。因此，这个语句是真的。
3. 第三个语句 (2, {1}) < (2, {2, 3}) 包含条件 {1} {2, 3}。因此，这个语句是假的。
4. 同样，第四个语句 (3, {1, 3}) < (3, {2, 3}) 包含条件 {1, 3} {2, 3}。因此，这个语句是假的。
5. 最后一个语句 (3, {1, 3}) < (3, {1, 2, 3}) 包含条件 3 = 3 且 {1, 3} {1, 2, 3}。因此，这个语句是真的。

例 6：在此例中，有两个偏序集 (B, |) 和 P(B)，其中 B = {2, 3, 4, 8}，"|"。这里 | 用于表示整除关系，P(B) 用于表示 B 的幂集。这里我们有一个具有小于关系 (<) 的字典序，它定义在笛卡尔积 B * P(B) 上。现在我们必须找出以下语句是真还是假。

1. (2, φ) < (3, {4, 8})
2. (2, {4}) < (4, {3, 8})
3. (2, {4}) < (2, {3, 4, 8})
4. (4, {2, 3}) < (4, {3, 4})
5. (8, {1, 3}) < (4, {1, 2, 3})

解决方案

1. 第一个语句 (2, φ) < (3, {4, 8}) 包含条件 2 不能整除 3。因此，这个语句是假的。
2. 第二个语句 (2, {4}) < (4, {3, 8}) 包含条件 2 整除 4（尽管 {4} {3, 8}）。因此，这个语句是真的。
3. 第三个语句 (2, {4}) < (2, {3, 4, 8}) 包含条件 2 = 2 且 {4} {3, 4, 8}。因此，这个语句是真的。
4. 第四个语句 (4, {2, 3}) < (4, {3, 4}) 包含条件 4 = 4，但 {2, 3} {3, 4}。因此，这个语句是假的。
5. 最后一个语句 (8, {1, 3}) < (4, {1, 2, 3}) 包含条件 8 不能整除 4。因此，这个语句是假的。

重要提示

有一些与字典序相关的重要点，其中一些描述如下：

• 我们可以通过递归地应用此定义，轻松地将字典序扩展到任意长度的笛卡尔积。我们将通过观察 A * B * C = A * (B * C) 来实现这一点。
• 如果我们将字典序应用于排列，它将按数字顺序或字母顺序增加符号列表。例如：假设我们有 {1, 2, 3} 的排列。这些排列的字典序是 123, 132, 213, 231, 312 和 321。
• 当我们将字典序应用于子集时，我们可以根据最小元素对两个子集进行排序。例如：假设我们有 {1, 2, 3} 的子集。这些子集的字典序是 {}, {1}, {1, 2}, {1, 2, 3}, {1, 3}, {2}, {2, 3}, {3}。