跳至內容

逆序對

維基百科,自由的百科全書
這個置換中的一個逆序對,表示為位置對(2,4)或元素對(5,2)。
這個置換的逆序,使用基於位置表示法表示為:(1, 3), (1, 4), (2, 3), (2, 4)和(2, 5);
或者使用基於元素表示法表示為:(3, 1), (3, 2), (5, 1), (5, 2)和(5, 4)。

計算機科學離散數學中,一個序列的逆序(inversion),是失去自然次序的元素對。

定義

逆序

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

為一個排列,如果而且, 這個位置(有稱為「序位」)對[1][2],或者這個元素對[3][4][5],被稱為是的一個逆序。

逆序集是所有逆序的集合。一個排列的使用基於位置表示法的逆序集,相同於其反向排列的使用基於元素表示法的逆序集,只有每個有序對的兩個分量交換位置,反之亦然[6]

通常逆序是對於排列的定義,但也可以用於序列: 設是一個序列(或多重集排列[7])。如果而且, 這個位置對[7][8],或者這個元素對[9],被稱為是的一個逆序。

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

逆序數

序列逆序數[10],是逆序集的,它常用於量度排列[5]或序列[9]的已排序程度(有時叫做預排序度presortedness)。逆序數在之間,含二者。

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

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

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

目前求逆序對數目比較普遍的方法,是利用歸併排序做到時間複雜度;也可以利用樹狀數組、線段樹來實現這種基礎功能。複雜度均為

逆序有關的向量

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

本文將逆序向量記為[13],其它的兩個向量有時分別稱為「左」和「右」逆序向量;為了避免與前面的逆序向量混淆,本文將另兩個分別稱為「左逆序計數」和「右逆序計數」。左逆序計數是以反向colexicographic次序的排列[14],右逆序計數則是以字典序的排列。

Rothe圖

逆序向量
採用基於元素的定義,是有序對較小(右)分量為的逆序數[3]

是在之中於之前,大於的元素的數量。

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

是在之中於之前,大於的元素的數量。

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

左逆序計數
採用基於位置的定義,是有序對較大(右)分量為的逆序數。

是在之中於之前,大於的元素的數量。

右逆序計數,通常稱為Lehmer碼
採用基於位置的定義,是有序對較小(左)分量為的逆序數。

之中於之後,小於的元素的數量。

之間的關係:

的第一個數字和的最後一個數字總是,可以省略。

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

之間的關係:

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

四個元素的6種可能逆序

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

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
p-b #
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 S4

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

參見

引用

  1. ^ Aigner 2007,第27頁.
  2. ^ Comtet 1974,第237頁.
  3. ^ 3.0 3.1 Knuth 1973,第11頁.
  4. ^ Pemmaraju & Skiena 2003,第69頁.
  5. ^ 5.0 5.1 Vitter & Flajolet 1990,第459頁.
  6. ^ 6.0 6.1 Gratzer 2016,第221頁.
  7. ^ 7.0 7.1 Bóna 2012,第57頁.
  8. ^ Cormen et al. 2001,第39頁.
  9. ^ 9.0 9.1 Barth & Mutzel 2004,第183頁.
  10. ^ Mannila 1985.
  11. ^ Mahmoud 2000,第284頁.
  12. ^ Kleinberg & Tardos 2005,第225頁.
  13. ^ Weisstein, Eric W. "Inversion Vector"頁面存檔備份,存於互聯網檔案館) From MathWorld--A Wolfram Web Resource
  14. ^ Reverse colex order of finitary permutations (OEIS數列A055089

參考書目

延伸閱讀

  • Margolius, Barbara H. Permutations with Inversions. Journal of Integer Sequences. 2001, 4. 

預排序度測度