字典序
| 字典序 | |
|---|---|
| 术语名称 | 字典序 |
| 英语名称 | lexicographic order |
| 别名 | lexicographical order, lexical order, lex order, dictionary order |
字典序(lexicographic(al) order, dictionary order, 简称 lex order)是元组或序列上的一种序关系。 按照从左到右顺序逐个元素比较，按照首个不同元素判断两序列的序关系，认为首个不同元素更小或在遇到不同元素前率先结束的序列先于另一序列。 字典和百科全书中往往使用这一顺序在特定语言的字母表上排列词条，称为字母序(alphabetical order)，字典序是字母序在任意给定集合上的泛化。
定义
| 字典序 | |
|---|---|
| 关系名称 | 字典序 |
| 关系符号 | |
| Latex | |
| 关系对象 | 序列 |
| 关系元数 | 2 |
| 类型 | 全序 |
| 字典序 | |
|---|---|
| 关系名称 | 字典序 |
| 关系符号 | |
| Latex | |
| 关系对象 | 元组 |
| 关系元数 | 2 |
| 类型 | 全序 |
对语言 [math]\displaystyle{ L }[/math] ，记其字母表为 [math]\displaystyle{ A }[/math] ，其上有一个全序 [math]\displaystyle{ \leq }[/math] （或给定对应的严格全序 [math]\displaystyle{ \lt }[/math] ）， 可定义序列（或有限的元组） [math]\displaystyle{ a = a_1 a_2 \cdots }[/math] 和 [math]\displaystyle{ b = b_1 b_2 \cdots }[/math] 上的关系 [math]\displaystyle{ \leq_\mathrm{lex} }[/math] 满足以下条件：
- 若 [math]\displaystyle{ a }[/math] 是 [math]\displaystyle{ b }[/math] 的前缀，则 [math]\displaystyle{ a \lt _\mathrm{lex} b }[/math] ；若 [math]\displaystyle{ b }[/math] 是 [math]\displaystyle{ a }[/math] 的前缀，则 [math]\displaystyle{ b \lt _\mathrm{lex} a }[/math] 。
- 否则，若有 [math]\displaystyle{ i }[/math] 是满足 [math]\displaystyle{ a_i \neq b_i }[/math] 的最小下标，则：
- 若 [math]\displaystyle{ a_i \lt b_i }[/math] 则 [math]\displaystyle{ a \lt _\mathrm{lex} b }[/math] ；
- 若 [math]\displaystyle{ a_i \gt b_i }[/math] 则 [math]\displaystyle{ b \lt _\mathrm{lex} a }[/math] 。
- 否则，两序列元素必对应相同，则 [math]\displaystyle{ a =_\mathrm{lex} b }[/math] 。
这一定义也可以用在笛卡尔积 [math]\displaystyle{ A_1\times A_2\times A_3\times\cdots }[/math] 中的两个序列或元组间，要求其中每个集合上都有这样的全序。
有时也允许字母表中的序关系为弱序，类似于现实中几个变体字母在字母表中有同一顺序，此时仍依此定义。
性质
- 若字母表上的序是一个全序，字典序一定也是一个全序。
- 若字母表上的序是一个良序，有限序列上的字典序一定也是一个良序。
- 但即使字母表上的序是一个良序，无穷序列上字典序也不一定是良序，因为无穷序列集合可能存在无穷下降链，找不到最小元。