逆序对

<image>

在计算机科学和离散数学中，一个序列的逆序（inversion）对，是失去自然次序的元素对。

## 定义

### 逆序

<image>

设$\ \pi \ $为一个排列，如果$\ i < j \ $而且$\ \pi(i) > \pi(j) \ $。

这个位置（有称为“序位”）对$\ (i, j) \ $，或者这个元素对$\ \bigl(\pi(i), \pi(j)\bigr) \ $，被称为是$\ \pi \ $的一个逆序。

逆序集是所有逆序的集合。一个排列$\ \pi \ $的使用基于位置表示法的逆序集，相同于其反向排列$\ \pi^{-1} \ $的使用基于元素表示法的逆序集，只有每个有序对的两个分量交换位置，反之亦然。

通常逆序是对于排列的定义，但也可以用于序列：

设$\ S \ $是一个序列（或多重集排列）。如果$\ i < j \ $而且$\ S(i) > S(j) \ $。

这个位置对$\ (i, j) \ $，或者这个元素对$\ \bigl(S(i), S(j)\bigr) \ $，被称为是$\ S \ $的一个逆序。

对于序列，根据基于元素定义的逆序不是唯一性的，因为不同的位置对上可能有相同的值对。

### 逆序数

序列$\ X=\langle x_1,\dots,x_n\rangle \ $的逆序数$\ \mathtt{inv}(X) \ $，是逆序集的势，它常用于量度排列或序列的已排序程度（有时叫做预排序度presortedness）。逆序数在$\ 0 \ $至$\ \frac{n(n-1)}2 \ $之间，含二者。

在一个排列的箭头指向图中，它是箭头指向相交叉的数，也是从单位排列而得到的Kendall tau距离，以及每个与逆序有关的向量之和，它们在后面章节中定义。

对于逆序数，基于位置与基于元素定义之间的分别并不重要，因为排列及其反向排列都具有相同的逆序数。

其它测量（预先）排序程度的方式，包括了为排好序列而从序列中可以删除元素的最小数量，对序列所“运行”排序的次数和长度，每个元素在已排序位置之上的距离总和（Spearman footrule），以及排序过程中必需的最少交换次数。比较排序算法计算逆序数的时间为$\ O(n \log n) \ $。

目前求逆序对数目比较普遍的方法，是利用归并排序做到$\ O(n \log n) \ $的时间复杂度；也可以利用树状数组、线段树来实现这种基础功能。复杂度均为$\ O(n \log n) \ $。

### 逆序有关的向量

有三个类似的向量用于将排列的逆序，压缩到能唯一确定它的这个向量中。它们通常被称为逆序向量或Lehmer码。这里的定义及公式来源于逆序 (离散数学)。

本文将逆序向量记为$\ v \ $，其它的两个向量有时分别称为“左”和“右”逆序向量；为了避免与前面的逆序向量混淆，本文将另两个分别称为“左逆序计数”$\ l \ $和“右逆序计数”$\ r \ $。左逆序计数是以反向colexicographic次序的排列，右逆序计数则是以字典序的排列。

<image>

逆序向量$\ v \ $：采用基于元素的定义，$\ v(i) \ $是有序对较小（右）分量为$\ i \ $的逆序数。

$\ v(i) \ $是在$\ \pi \ $之中于$\ i \ $之前，大于$\ i \ $的元素的数量。

$$v(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi^{-1}(k) < \pi^{-1}(i) \}$$

其更符合直觉的定义方式为：

$\ v\bigl(\pi(i)\bigr) \ $是在$\ \pi \ $之中于$\ \pi(i) \ $之前，大于$\ \pi(i) \ $的元素的数量。

$$v\bigl(\pi(i)\bigr) ~~=~~ \# \{ k \mid k < i ~\land~ \pi(k) > \pi(i) \} ~~=~~ l(i)$$

后者定义也适用于没有反向对应者的序列。

左逆序计数$\ l \ $：采用基于位置的定义，$\ l(i) \ $是有序对较大（右）分量为$\ l(i) \ $的逆序数。

$\ l(i) \ $是在$\ \pi(i) \ $之中于$\ \pi(i) \ $之前，大于$\ \pi(i) \ $的元素的数量。

$$l(i) ~~=~~ \# \left\{ k \mid k < i ~\land~ \pi(k) > \pi(i) \right\}$$

右逆序计数$\ r \ $，通常称为Lehmer码：采用基于位置的定义，$\ r(i) \ $是有序对较小（左）分量为$\ i \ $的逆序数。

$\ r(i) \ $是$\ \pi(i) \ $之中于$\ \pi(i) \ $之后，小于$\ \pi(i) \ $的元素的数量。

$$r(i) ~~=~~ \# \{ k \mid k > i ~\land~ \pi(k) < \pi(i) \}$$

$\ l \ $和$\ v \ $之间的关系：

$$v(i) ~~=~~ l\bigl(\pi^{-1}(i)\bigr)$$ $$l(i) ~~=~~ v\bigl(\pi(i)\bigr)$$

$\ l \ $的第一个数字和$\ v \ $的最后一个数字总是$\ 0 \ $，可以省略。

Rothe图可以协助找出$\ v \ $和$\ r \ $。Heinrich August Rothe图是以黑点来表示1的排列矩阵，每一个位置上若为逆序（通常以叉号表示），则在其右侧与下方即有一点。$\ r(i) \ $是图中第$\ i \ $列排列逆序的加总，而$\ v(i) \ $是$\ i \ $栏中排列逆序的加总。排列矩阵的逆矩阵即是此矩阵的转置矩阵，因此某一排列的$\ v \ $即是它转置矩阵的$\ r \ $，反之亦然。

$\ r \ $和$\ l \ $之间的关系：

$$\pi(i) ~~=~~ i + r(i) - l(i)$$

## 范例：四个元素的全部排列

<image>

下面可排序表显示了四个元素的集合，它的逆序集会有不同位置的24种排列、逆序相关向量和逆序数（右栏是它的反向排列，用于以colex排序）。可以看出$\ v \ $和$\ l \ $的位数总是相同，而$\ l \ $和$\ r \ $与位逆序集有关。

最右侧栏是排列左上右下对角线的总和，如三角形图示，以及$\ r \ $是左下右上对角线的总和（配对在下降对角线中其右侧都是$\ 2,3,4 \ $组成，而在上升对角线中的左侧都是$\ 1,2,3 \ $组成）。

此表中$\ \pi \ $的预设排序是反向colex次序，这与$\ l \ $的colex次序相同。$\ \pi \ $的字典序与$\ r \ $的字典序相同。

用于比较的三个元素全部排列表

## 排列的弱次序

<image>

n物品排列的集合其部分次序的结构，称为排列的弱次序，而构成格。

以逆序集的子集关系绘出的哈斯图，则构成了称为permutohedron的骨架。

如果依位置将某一排列分配给每个逆序集，所得到的排序是permutohedron的次序，其中的边对应于连续两元素的交换。这是排列的弱排序。The identity is its minimum, and the permutation formed by reversing the identity is its maximum.

如果依元素将某一排列分配给每个逆序集，所得到的排序将是凯莱图的次序，其中的边对应于连续两元素的交换。对称组的凯莱图与其permutohedron相似，但是每个排列由其反向替换。