逆序對

在計算機科學和離散數學中，一個序列的逆序（inversion）對，是失去自然次序的元素對。

這個置換中的一個逆序對，表示為位置對（2,4）或元素對（5,2）。
這個置換的逆序，使用基於位置表示法表示為：(1, 3), (1, 4), (2, 3), (2, 4)和(2, 5)；
或者使用基於元素表示法表示為：(3, 1), (3, 2), (5, 1), (5, 2)和(5, 4)。

定義

逆序

一個四元素置換的從基於位置逆序到基於元素逆序的映射。

設${\displaystyle \ \pi \ }$為一個排列，如果${\displaystyle \ i<j\ }$而且${\displaystyle \ \pi (i)>\pi (j)\ }$， 這個位置（有稱為「序位」）對${\displaystyle \ (i,j)\ }$^[1][2]，或者這個元素對${\displaystyle \ {\bigl (}\pi (i),\pi (j){\bigr )}\ }$^[3][4][5]，被稱為是${\displaystyle \ \pi \ }$的一個逆序。

逆序集是所有逆序的集合。一個排列${\displaystyle \ \pi \ }$的使用基於位置表示法的逆序集，相同於其反向排列${\displaystyle \ \pi ^{-1}\ }$的使用基於元素表示法的逆序集，只有每個有序對的兩個分量交換位置，反之亦然^[6]。

通常逆序是對於排列的定義，但也可以用於序列： 設${\displaystyle \ S\ }$是一個序列（或多重集排列^[7]）。如果${\displaystyle \ i<j\ }$而且${\displaystyle \ S(i)>S(j)\ }$， 這個位置對${\displaystyle \ (i,j)\ }$^[7][8]，或者這個元素對${\displaystyle \ {\bigl (}S(i),S(j){\bigr )}\ }$^[9]，被稱為是${\displaystyle \ S\ }$的一個逆序。

對於序列，根據基於元素定義的逆序不是唯一性的，因為不同的位置對上可能有相同的值對。

逆序數

序列${\displaystyle \ X=\langle x_{1},\dots ,x_{n}\rangle \ }$的逆序數${\displaystyle \ {\mathtt {inv}}(X)\ }$^[10]，是逆序集的勢，它常用於量度排列^[5]或序列^[9]的已排序程度（有時叫做預排序度presortedness）。逆序數在${\displaystyle \ 0\ }$至${\displaystyle \ {\frac {n(n-1)}{2}}\ }$之間，含二者。

在一個排列的箭頭指向圖中，它是箭頭指向相交叉的數^[6]，也是從單位排列而得到的Kendall tau距離（英語：Kendall tau distance），以及每個與逆序有關的向量之和，它們在後面章節中定義。

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

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

目前求逆序對數目比較普遍的方法，是利用歸併排序做到${\displaystyle \ O(n\log n)\ }$的時間複雜度；也可以利用樹狀數組、線段樹來實現這種基礎功能。複雜度均為${\displaystyle \ O(n\log n)\ }$。

逆序有關的向量

有三個類似的向量用於將排列的逆序，壓縮到能唯一確定它的這個向量中。它們通常被稱為逆序向量或Lehmer碼（英語：Lehmer code）。這裡的定義及公式來源於逆序 (離散數學)。

本文將逆序向量記為${\displaystyle \ v\ }$^[13]，其它的兩個向量有時分別稱為「左」和「右」逆序向量；為了避免與前面的逆序向量混淆，本文將另兩個分別稱為「左逆序計數」${\displaystyle \ l\ }$和「右逆序計數」${\displaystyle \ r\ }$。左逆序計數是以反向colexicographic次序的排列^[14]，右逆序計數則是以字典序的排列。

Rothe圖

逆序向量${\displaystyle \ v\ }$：
採用基於元素的定義，${\displaystyle \ v(i)\ }$是有序對較小（右）分量為${\displaystyle \ i\ }$的逆序數^[3]。

${\displaystyle \ v(i)\ }$是在${\displaystyle \ \pi \ }$之中於${\displaystyle \ i\ }$之前，大於${\displaystyle \ i\ }$的元素的數量。

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

其更符合直覺的定義方式為：

${\displaystyle \ v{\bigl (}\pi (i){\bigr )}\ }$是在${\displaystyle \ \pi \ }$之中於${\displaystyle \ \pi (i)\ }$之前，大於${\displaystyle \ \pi (i)\ }$的元素的數量。

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

後者定義也適用於沒有反向對應者的序列。

左逆序計數${\displaystyle \ l\ }$：
採用基於位置的定義，${\displaystyle \ l(i)\ }$是有序對較大（右）分量為${\displaystyle \ l(i)\ }$的逆序數。

${\displaystyle \ l(i)\ }$是在${\displaystyle \ \pi (i)\ }$之中於${\displaystyle \ \pi (i)\ }$之前，大於${\displaystyle \ \pi (i)\ }$的元素的數量。

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

右逆序計數${\displaystyle \ r\ }$，通常稱為Lehmer碼：
採用基於位置的定義，${\displaystyle \ r(i)\ }$是有序對較小（左）分量為${\displaystyle \ i\ }$的逆序數。

${\displaystyle \ r(i)\ }$是${\displaystyle \ \pi (i)\ }$之中於${\displaystyle \ \pi (i)\ }$之後，小於${\displaystyle \ \pi (i)\ }$的元素的數量。

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

${\displaystyle \ l\ }$和${\displaystyle \ v\ }$之間的關係：

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

${\displaystyle l(i)~~=~~v{\bigl (}\pi (i){\bigr )}}$

${\displaystyle \ l\ }$的第一個數字和${\displaystyle \ v\ }$的最後一個數字總是${\displaystyle \ 0\ }$，可以省略。

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

${\displaystyle \ r\ }$和${\displaystyle \ l\ }$之間的關係：

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

範例：四個元素的全部排列

四個元素的6種可能逆序

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

用於比較的三個元素全部排列表
0 1 2 3 4 5 ${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ p-b ${\displaystyle r}$ # 0 123 321 000 000 000 000 000 000 0 1 213 312 100 001 010 010 100 001 1 2 132 231 010 010 100 001 010 010 1 3 312 213 110 011 110 011 200 002 2 4 231 132 200 002 200 002 110 011 2 5 321 123 210 012 210 012 210 012 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

${\displaystyle \pi }$ ${\displaystyle v}$ ${\displaystyle l}$ p-b ${\displaystyle r}$ # 0 1234 4321 0000 0000 0000 0000 0000 0000 0 1 2134 4312 1000 0001 0010 0100 1000 0001 1 2 1324 4231 0100 0010 0100 0010 0100 0010 1 3 3124 4213 1100 0011 0110 0110 2000 0002 2 4 2314 4132 2000 0002 0200 0020 1100 0011 2 5 3214 4123 2100 0012 0210 0120 2100 0012 3 6 1243 3421 0010 0100 1000 0001 0010 0100 1 7 2143 3412 1010 0101 1010 0101 1010 0101 2 8 1423 3241 0110 0110 1100 0011 0200 0020 2 9 4123 3214 1110 0111 1110 0111 3000 0003 3 10 2413 3142 2010 0102 1200 0021 1200 0021 3 11 4213 3124 2110 0112 1210 0121 3100 0013 4 12 1342 2431 0200 0020 2000 0002 0110 0110 2 13 3142 2413 1200 0021 2010 0102 2010 0102 3 14 1432 2341 0210 0120 2100 0012 0210 0120 3 15 4132 2314 1210 0121 2110 0112 3010 0103 4 16 3412 2143 2200 0022 2200 0022 2200 0022 4 17 4312 2134 2210 0122 2210 0122 3200 0023 5 18 2341 1432 3000 0003 3000 0003 1110 0111 3 19 3241 1423 3100 0013 3010 0103 2110 0112 4 20 2431 1342 3010 0103 3100 0013 1210 0121 4 21 4231 1324 3110 0113 3110 0113 3110 0113 5 22 3421 1243 3200 0023 3200 0023 2210 0122 5 23 4321 1234 3210 0123 3210 0123 3210 0123 6

排列的弱次序

對稱群的Permutohedron S₄

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

參見

• 階乘進制
• 置換群
• 置換的奇偶性