逆序對

<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相似，但是每個排列由其反向替換。