逆序对

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

定義
逆序
設\ \pi \ 為一個排列，如果\ i 而且 \ \pi(i) > \pi(j) \ ，
這個位置（有称为“序位”）对 \ (i, j) \ ，或者這个元素对 \ \bigl(\pi(i), \pi(j)\bigr) \ ，被稱為是 \ \pi \ 的一個逆序。

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

通常逆序是對於排列的定義，但也可以用於序列：
設 \ S \ 是一個序列（或多重集排列）。如果 \ i 而且 \ 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 \ 之间，含二者。

在一個排列的箭頭指向圖中，它是箭頭指向相交叉的數，也是從单位排列而得到的，以及每個与逆序有關的向量之和，它们在后面章节中定義。

對於逆序數，基于位置与基于元素定義之间的分別並不重要，因為排列及其反向排列都具有相同的逆序數。

其它測量（預先）排序程度的方式，包括了為排好序列而從序列中可以刪除元素的最小數量，對序列所“運行”排序的次數和長度，每個元素在已排序位置之上的距離總和（Spearman footrule），以及排序過程中必需的最少交換次數。比較排序算法計算逆序數的時間為 \ O(n \log n) \ 。

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

逆序有關的向量
有三個類似的向量用於將排列的逆序，壓縮到能唯一確定它的这个向量中。它們通常被稱為逆序向量或**'。这里的定义及公式来源于逆序 (离散数学)。

本文將逆序向量記為 \ v \ ，其它的兩個向量有時分別稱為“左”和“右”逆序向量；為了避免與前面的逆序向量混淆，本文將另兩個分別稱為“左逆序計數” \ l \ 和“右逆序計數” \ r \ 。左逆序計數是以反向colexicographic次序的排列，右逆序計數則是以字典序的排列。

逆序向量 \ v \ ：
采用基于元素的定義， \ v(i) \ 是有序对較小（右）分量為 \ i \ 的逆序數。
: \ v(i) \ 是在 \ \pi \ 之中于 \ i \ 之前，大于 \ i \ 的元素的數量。
:v(i) = \# \{ k \mid k > i ~\land~ \pi^{-1}(k)
其更符合直觉的定义方式为：
: \ v\bigl(\pi(i)\bigr) \ 是在 \ \pi \ 之中于 \ \pi(i) \ 之前，大于 \ \pi(i) \ 的元素的数量。
:v\bigl(\pi(i)\bigr) = \# \{ k \mid k \pi(i) \} = l(i)
后者定义也适用于没有反向对应者的序列。

左逆序計數 \ l \ ：
采用基于位置的定義， \ l(i) \ 是有序对較大（右）分量為 \ l(i) \ 的逆序數。
: \ l(i) \ 是在 \ \pi(i) \ 之中于 \ \pi(i) \ 之前，大于 \ \pi(i) \ 的元素的數量。
:l(i) = \# \left\{ k \mid 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)

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

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

Rothe圖可以協助找出 \ v \ 和 \ r \ 。圖是以黑點來表示1的排列矩陣，每一個位置上若為逆序（通常以叉號表示），則在其右側與下方即有一點。 \ r(i) \ 是圖中第 \ i \ 列排列逆序的加總，而 \ v(i) \ 是 \ i \ 欄中排列逆序的加總。排列矩陣的逆矩阵即是此矩陣的轉置矩陣，因此某一排列的 \ v \ 即是它轉置矩陣的 \ r \ ，反之亦然。

\ r \ 和 \ l \ 之间的关系：
:\pi(i) = i + r(i) - l(i)

範例：四個元素的全部排列
下面可排序表顯示了四個元素的集合，它的逆序集會有不同位置的24種排列、逆序相關向量和逆序數（右欄是它的反向排列，用於以colex排序）。可以看出 \ v \ 和 \ l \ 的位數總是相同，而 \ l \ 和 \ r \ 與位逆序集有關。
最右側欄是排列左上右下對角線的總和，如三角形圖示，以及 \ r \ 是左下右上對角線的總和（配對在下降對角線中其右側都是 \ 2,3,4 \ 組成，而在上升對角線中的左側都是\ 1,2,3 \ 組成）。
此表中 \ \pi \ 的預設排序是反向colex次序，這與 \ l \ 的colex次序相同。 \ \pi \ 的字典序與 \ r \ 的字典序相同。

排列的弱次序
的Permutohedron S4]]
n物品排列的集合其部份次序的結構，稱為排列的弱次序，而構成格。
以逆序集的子集關係繪出的哈斯圖，則構成了稱為permutohedron的骨架。
如果依位置將某一排列分配給每個逆序集，所得到的排序是permutohedron的次序，其中的邊對應於連續兩元素的交換。這是排列的弱排序。The identity is its minimum, and the permutation formed by reversing the identity is its maximum.
如果依元素將某一排列分配給每個逆序集，所得到的排序將是凱萊圖的次序，其中的邊對應於連續兩元素的交換。對稱組的凱萊圖與其permutohedron相似，但是每個排列由其反向替換。

参见

阶乘进制
置换群
置换的奇偶性

引用
参考书目
*
*
*
*
*
*
*
*
*
*
*

评论 (0)