反向字典序：修订间差异
创建页面，内容为“分类:序理论{{DEFAULTSORT:fan3xiang4zi4dian3xu4}} {{#seo: |keywords=反向字典序, 逆字典序, 右起字典序, 后缀字典序 |description=本文介绍反向字典序的定义、性质和应用，包括在字符序列和数学结构上的反向字典序构造，及其与字典序的区别与联系。 |modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}} |published_time=2025-10-26 }} {{InfoBox |name=反向字典序 |eng_name=colexicogr…” |
无编辑摘要 |
||
| （未显示同一用户的2个中间版本） | |||
| 第11行： | 第11行： | ||
|aliases=colex order,reverse lexicographic order | |aliases=colex order,reverse lexicographic order | ||
}} | }} | ||
{{非标准翻译}} | |||
'''反向字典序'''('''colexicographic order''', 简称 '''colex order''')是[[字典序]]的一种变体，比较序列时从右向左逐个元素比较，而非传统的从左向右。 | '''反向字典序'''('''colexicographic order''', 简称 '''colex order''')是[[字典序]]的一种变体，比较序列时从右向左逐个元素比较，而非传统的从左向右。 | ||
<blockquote> | |||
本文的内容是一种将序列逆序的字典序所构成的顺序，不是字典序的逆序。 | |||
</blockquote> | |||
== 定义 == | == 定义 == | ||
| 第27行： | 第34行： | ||
对[[语言]] <math>L</math> ，记其字母表为 <math>A</math> ，其上有一个[[全序]] <math>\leq</math> （或给定对应的[[严格全序]] <math><</math> ）， | 对[[语言]] <math>L</math> ，记其字母表为 <math>A</math> ，其上有一个[[全序]] <math>\leq</math> （或给定对应的[[严格全序]] <math><</math> ）， | ||
可定义序列（或有限的元组） <math>a = a_1 a_2 \cdots a_m</math> 和 <math>b = b_1 b_2 \cdots b_n</math> 上的关系 <math>\leq_\mathrm{colex}</math> 满足以下条件： | 可定义序列（或有限的元组） <math>a = a_1 a_2 \cdots a_m</math> 和 <math>b = b_1 b_2 \cdots b_n</math> 上的关系 <math>\leq_\mathrm{colex}</math> 满足以下条件： | ||
* 若 <math>a</math> 是 <math>b</math> 的后缀，则 <math>a <_\mathrm{ | * 若 <math>a</math> 是 <math>b</math> 的后缀，则 <math>a <_\mathrm{colex} b</math> ；若 <math>b</math> 是 <math>a</math> 的后缀，则 <math>b <_\mathrm{colex} a</math> 。 | ||
* 否则，若有 <math>i</math> 是满足 <math>a_{m-i} \neq b_{n-i}</math> 的最小值，此时取得元素不同的最大下标，则： | * 否则，若有 <math>i</math> 是满足 <math>a_{m-i} \neq b_{n-i}</math> 的最小值，此时取得元素不同的最大下标，则： | ||
** 若 <math>a_{m-i} < b_{n-i}</math> 则 <math>a <_\mathrm{colex} b</math> ； | ** 若 <math>a_{m-i} < b_{n-i}</math> 则 <math>a <_\mathrm{colex} b</math> ； | ||
| 第39行： | 第46行： | ||
== 与字典序的区别 == | == 与字典序的区别 == | ||
* | * 字典序：从左向右比较，首元素权重最高。允许定义在无穷序列上。 | ||
* | * 反向字典序：从右向左比较，末元素权重最高。无法定义在无穷序列上。 | ||
2025年10月26日 (日) 15:37的最新版本
| 反向字典序 | |
|---|---|
| 术语名称 | 反向字典序 |
| 英语名称 | colexicographic order |
| 别名 | colex order, reverse lexicographic order |
本条目没有一致可信的中文译名。
反向字典序(colexicographic order, 简称 colex 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 a_m }[/math] 和 [math]\displaystyle{ b = b_1 b_2 \cdots b_n }[/math] 上的关系 [math]\displaystyle{ \leq_\mathrm{colex} }[/math] 满足以下条件：
- 若 [math]\displaystyle{ a }[/math] 是 [math]\displaystyle{ b }[/math] 的后缀，则 [math]\displaystyle{ a \lt _\mathrm{colex} b }[/math] ；若 [math]\displaystyle{ b }[/math] 是 [math]\displaystyle{ a }[/math] 的后缀，则 [math]\displaystyle{ b \lt _\mathrm{colex} a }[/math] 。
- 否则，若有 [math]\displaystyle{ i }[/math] 是满足 [math]\displaystyle{ a_{m-i} \neq b_{n-i} }[/math] 的最小值，此时取得元素不同的最大下标，则：
- 若 [math]\displaystyle{ a_{m-i} \lt b_{n-i} }[/math] 则 [math]\displaystyle{ a \lt _\mathrm{colex} b }[/math] ；
- 若 [math]\displaystyle{ a_{m-i} \gt b_{n-i} }[/math] 则 [math]\displaystyle{ b \lt _\mathrm{colex} a }[/math] 。
- 否则，两序列元素必对应相同，则 [math]\displaystyle{ a =_\mathrm{colex} b }[/math] 。
这一定义也可以用在笛卡尔积 [math]\displaystyle{ A_1\times A_2\times A_3\times\cdots\times A_n }[/math] 中的两个序列或元组间，要求其中每个集合上都有这样的全序。
有时也允许字母表中的序关系为弱序，类似于现实中几个变体字母在字母表中有同一顺序，此时仍依此定义。
与字典序的区别
- 字典序：从左向右比较，首元素权重最高。允许定义在无穷序列上。
- 反向字典序：从右向左比较，末元素权重最高。无法定义在无穷序列上。