查看“︁反向字典序”︁的源代码

[[分类:序理论]]{{DEFAULTSORT:fan3xiang4zi4dian3xu4}}
{{#seo:
|keywords=反向字典序, 逆字典序, 右起字典序, 后缀字典序
|description=本文介绍反向字典序的定义、性质和应用，包括在字符序列和数学结构上的反向字典序构造，及其与字典序的区别与联系。
|modified_time={{REVISIONYEAR}}-{{REVISIONMONTH}}-{{REVISIONDAY2}}
|published_time=2025-10-26
}}
{{InfoBox
|name=反向字典序
|eng_name=colexicographic order
|aliases=colex order,reverse lexicographic order
}}
'''反向字典序'''('''colexicographic order''', 简称 '''colex order''')是[[字典序]]的一种变体，比较序列时从右向左逐个元素比较，而非传统的从左向右。

== 定义 ==

{{Relation
|name=反向字典序
|operand_relation=序列
|prototype=全序
}}
{{Relation
|name=反向字典序
|operand_relation=元组
|prototype=全序
}}
对[[语言]] <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</math> 是 <math>b</math> 的后缀，则 <math>a <_\mathrm{lex} b</math> ；若 <math>b</math> 是 <math>a</math> 的后缀，则 <math>b <_\mathrm{lex} a</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>b <_\mathrm{colex} a</math> 。
* 否则，两序列元素必对应相同，则 <math>a =_\mathrm{colex} b</math> 。

这一定义也可以用在笛卡尔积 <math>A_1\times A_2\times A_3\times\cdots\times A_n</math> 中的两个序列或元组间，要求其中每个集合上都有这样的全序。

有时也允许字母表中的序关系为[[弱序]]，类似于现实中几个变体字母在字母表中有同一顺序，此时仍依此定义。

== 与字典序的区别 ==

* '''字典序'''：从左向右比较，首元素权重最高。允许定义在无穷序列上。
* '''逆字典序'''：从右向左比较，末元素权重最高。无法定义在无穷序列上。