逆序对

设A为一个有n个数字的有序集（n>1），其中所有数字各不相同。

一個排列逆序對的突顯，它可以由序位（2,4）或對位元素（5,2）表示。

如果存在正整數i, j使得1 ≤ i ＜ j ≤ n而且A[i] ＞ A[j]，則<A[i], A[j]>這一個有序對稱為A的一個逆序對，也称作逆序。逆序對的數量称作「逆序数」^[1]或「反序數」^[2]。

例如：数组<2,3,8,6,1>的逆序对为：<2,1> <3,1> <8,1> <8,6> <6,1>共5个逆序对。

对于<2,1>:1 ≤ 1 ＜ 5 ≤ 5 ,A[1] ＞A[5]，所以<A[1],A[5]>为一个合法的逆序对。

目前求逆序对数目比较普遍的方法是利用归并排序做到${\displaystyle O(n\log n)}$的时间复杂度。

当然，也可以利用树状数组、线段树来实现这种基础功能。复杂度均为${\displaystyle O(n\log n)}$。

定義

逆序

設${\displaystyle \pi }$ 為一個排列，如果${\displaystyle i<j}$ 而且${\displaystyle \pi (i)>\pi (j)}$ ， 這個序位${\displaystyle (i,j)}$ 或這一對元素${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$ 被稱為是${\displaystyle \pi }$ 的一個逆序。通常逆序是對於排列的定義，但也可以用於序列：

設${\displaystyle S}$ 是一個序列（或多重排列）。如果${\displaystyle i<j}$ 而且${\displaystyle S(i)>S(j)}$ ， 這個序位${\displaystyle (i,j)}$ 或這對元素${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$ 被稱為是${\displaystyle S}$ 的一個逆序。

對於根據元素組成的序列，逆序的定義不是唯一的，因為不同的序位上可能有相同的值對。逆序集是所有逆序的集合。一個排列依其序位而定義的逆序集是，它的反向排列依其序位而定義的逆序集，反之亦然，只是交換了配對的元素。

逆序數

逆序數是逆序集的基數，它常用於量度排列或序列的已排序程度。

在一個排列的箭頭指向圖中，它是箭頭指向相交叉的數，也是從自指(identity)排列而得到的Kendall tau距離，以及每個反向相關向量的和，如下列定義。

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

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

相關聯的逆序向量

有三個類似的向量用於將排列的逆序，壓縮到確定唯一的向量中。它們通常被稱為逆序向量或Lehmer碼。本文將逆序向量記為(${\displaystyle v}$ )，其它的兩個向量有時分別稱為左和右逆序向量；為了避免與前面的逆序向量混淆，本文將另兩個分別稱為左逆序計數${\displaystyle l}$ 和右逆序計數${\displaystyle r}$ 。左逆序計數是以反向colexicographic次序的排列，右逆序計數則是以字典次序的排列。

 

Rothe diagram

• 逆序向量${\displaystyle v}$ ：依據元素的定義，${\displaystyle v(i)}$ 是較小（右）分量為${\displaystyle i}$ 的逆序數。${\displaystyle v(i)}$ 是在${\displaystyle \pi }$ 之中的${\displaystyle i}$ 之前，元素較${\displaystyle i}$ 大的數量。

  ${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(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)}$ 是較小（左）分量為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)\}}$ 

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

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

 

四個元素可能的6種排列

下面可排序表顯示了四個元素的集合，它的逆序集會有不同位置的24種排列、逆序相關向量和逆序數（右欄是它的反向排列，用於以colex排序）。可以看出${\displaystyle v}$ 和${\displaystyle l}$ 的位數總是相同，而${\displaystyle l}$ 和${\displaystyle r}$ 與位逆序集有關。 最右側欄是排列左上右下對角線的總和，如三角形圖示，以及r是左下右上對角線的總和（配對在下降對角線中其右側都是2,3,4組成，而在上升對角線中的左側都是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相似，但是每個排列由其反向替換。

另見

參考

1. 王慧; 于海波. 线性代数. 上海: 上海交通大学出版社. 2018: 4. 
2. 高金泰. 高等代数考研600题精解. 成都: 西南交通大学出版社. 2017: 31.