逆序對
此條目需要精通或熟悉相關主題的編者參與及協助編輯。 (2014年4月8日) |
在計算機科學和離散數學中,一個序列的逆序(inversion)對,是失去自然次序的元素對。
![](http://images.weserv.nl/?url=//upload.wikimedia.org/wikipedia/commons/thumb/8/80/Inversion_qtl1.svg/260px-Inversion_qtl1.svg.png)
這個置換的逆序,使用基於位置表示法表示為:(1, 3), (1, 4), (2, 3), (2, 4)和(2, 5);
或者使用基於元素表示法表示為:(3, 1), (3, 2), (5, 1), (5, 2)和(5, 4)。
定義
逆序
設 為一個排列,如果 而且 , 這個位置(有稱為「序位」)對 [1][2],或者這個元素對 [3][4][5],被稱為是 的一個逆序。
逆序集是所有逆序的集合。一個排列 的使用基於位置表示法的逆序集,相同於其反向排列 的使用基於元素表示法的逆序集,只有每個有序對的兩個分量交換位置,反之亦然[6]。
通常逆序是對於排列的定義,但也可以用於序列: 設 是一個序列(或多重集排列[7])。如果 而且 , 這個位置對 [7][8],或者這個元素對 [9],被稱為是 的一個逆序。
對於序列,根據基於元素定義的逆序不是唯一性的,因為不同的位置對上可能有相同的值對。
逆序數
序列 的逆序數 [10],是逆序集的勢,它常用於量度排列[5]或序列[9]的已排序程度(有時叫做預排序度presortedness)。逆序數在 至 之間,含二者。
在一個排列的箭頭指向圖中,它是箭頭指向相交叉的數[6],也是從單位排列而得到的Kendall tau距離,以及每個與逆序有關的向量之和,它們在後面章節中定義。
對於逆序數,基於位置與基於元素定義之間的分別並不重要,因為排列及其反向排列都具有相同的逆序數。
其它測量(預先)排序程度的方式,包括了為排好序列而從序列中可以刪除元素的最小數量,對序列所「運行」排序的次數和長度,每個元素在已排序位置之上的距離總和(Spearman footrule),以及排序過程中必需的最少交換次數[11]。比較排序算法計算逆序數的時間為 [12]。
目前求逆序對數目比較普遍的方法,是利用歸併排序做到 的時間複雜度;也可以利用樹狀數組、線段樹來實現這種基礎功能。複雜度均為 。
逆序有關的向量
有三個類似的向量用於將排列的逆序,壓縮到能唯一確定它的這個向量中。它們通常被稱為逆序向量或Lehmer碼。這裡的定義及公式來源於逆序 (離散數學)。
本文將逆序向量記為 [13],其它的兩個向量有時分別稱為「左」和「右」逆序向量;為了避免與前面的逆序向量混淆,本文將另兩個分別稱為「左逆序計數」 和「右逆序計數」 。左逆序計數是以反向colexicographic次序的排列[14],右逆序計數則是以字典序的排列。
逆序向量 :
採用基於元素的定義, 是有序對較小(右)分量為 的逆序數[3]。
- 是在 之中於 之前,大於 的元素的數量。
其更符合直覺的定義方式為:
- 是在 之中於 之前,大於 的元素的數量。
後者定義也適用於沒有反向對應者的序列。
左逆序計數 :
採用基於位置的定義, 是有序對較大(右)分量為 的逆序數。
- 是在 之中於 之前,大於 的元素的數量。
右逆序計數 ,通常稱為Lehmer碼:
採用基於位置的定義, 是有序對較小(左)分量為 的逆序數。
- 是 之中於 之後,小於 的元素的數量。
和 之間的關係:
|
的第一個數字和 的最後一個數字總是 ,可以省略。
Rothe圖可以協助找出 和 。Rothe圖是以黑點來表示1的排列矩陣,每一個位置上若為逆序(通常以叉號表示),則在其右側與下方即有一點。 是圖中第 列排列逆序的加總,而 是 欄中排列逆序的加總。排列矩陣的逆矩陣即是此矩陣的轉置矩陣,因此某一排列的 即是它轉置矩陣的 ,反之亦然。
和 之間的關係:
範例:四個元素的全部排列
下面可排序表顯示了四個元素的集合,它的逆序集會有不同位置的24種排列、逆序相關向量和逆序數(右欄是它的反向排列,用於以colex排序)。可以看出 和 的位數總是相同,而 和 與位逆序集有關。 最右側欄是排列左上右下對角線的總和,如三角形圖示,以及 是左下右上對角線的總和(配對在下降對角線中其右側都是 組成,而在上升對角線中的左側都是 組成)。 此表中 的預設排序是反向colex次序,這與 的colex次序相同。 的字典序與 的字典序相同。
|
|
排列的弱次序
n物品排列的集合其部份次序的結構,稱為排列的弱次序,而構成格。 以逆序集的子集關係繪出的哈斯圖,則構成了稱為permutohedron的骨架。 如果依位置將某一排列分配給每個逆序集,所得到的排序是permutohedron的次序,其中的邊對應於連續兩元素的交換。這是排列的弱排序。The identity is its minimum, and the permutation formed by reversing the identity is its maximum. 如果依元素將某一排列分配給每個逆序集,所得到的排序將是凱萊圖的次序,其中的邊對應於連續兩元素的交換。對稱組的凱萊圖與其permutohedron相似,但是每個排列由其反向替換。
參見
引用
- ^ Aigner 2007,第27頁.
- ^ Comtet 1974,第237頁.
- ^ 3.0 3.1 Knuth 1973,第11頁.
- ^ Pemmaraju & Skiena 2003,第69頁.
- ^ 5.0 5.1 Vitter & Flajolet 1990,第459頁.
- ^ 6.0 6.1 Gratzer 2016,第221頁.
- ^ 7.0 7.1 Bóna 2012,第57頁.
- ^ Cormen et al. 2001,第39頁.
- ^ 9.0 9.1 Barth & Mutzel 2004,第183頁.
- ^ Mannila 1985.
- ^ Mahmoud 2000,第284頁.
- ^ Kleinberg & Tardos 2005,第225頁.
- ^ Weisstein, Eric W. "Inversion Vector" (頁面存檔備份,存於網際網路檔案館) From MathWorld--A Wolfram Web Resource
- ^ Reverse colex order of finitary permutations (OEIS數列A055089)
參考書目
- Aigner, Martin. Word Representation. A course in enumeration. Berlin, New York: Springer. 2007. ISBN 978-3642072536.
- Barth, Wilhelm; Mutzel, Petra. Simple and Efficient Bilayer Cross Counting. Journal of Graph Algorithms and Applications. 2004, 8 (2): 179–194. doi:10.7155/jgaa.00088 .
- Bóna, Miklós. 2.2 Inversions in Permutations of Multisets. Combinatorics of permutations. Boca Raton, FL: CRC Press. 2012. ISBN 978-1439850510.
- Comtet, Louis. 6.4 Inversions of a permutation of [n]. Advanced combinatorics; the art of finite and infinite expansions. Dordrecht,Boston: D. Reidel Pub. Co. 1974. ISBN 9027704414.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford. Introduction to Algorithms 2nd. MIT Press and McGraw-Hill. 2001. ISBN 0-262-53196-8.
- Gratzer, George. 7-2 Basic objects. Lattice theory. special topics and applications. Cham, Switzerland: Birkhäuser. 2016. ISBN 978-3319442358.
- Kleinberg, Jon; Tardos, Éva. Algorithm Design. 2005. ISBN 0-321-29535-8.
- Knuth, Donald. 5.1.1 Inversions. The Art of Computer Programming. Addison-Wesley Pub. Co. 1973. ISBN 0201896850.
- Mahmoud, Hosam Mahmoud. Sorting Nonrandom Data. Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization 54. Wiley-IEEE. 2000. ISBN 978-0-471-32710-3.
- Pemmaraju, Sriram V.; Skiena, Steven S. Permutations and combinations. Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. 2003. ISBN 978-0-521-80686-2.
- Vitter, J.S.; Flajolet, Ph. Average-Case Analysis of Algorithms and Data Structures. van Leeuwen, Jan (編). Algorithms and Complexity 1 2nd. Elsevier. 1990. ISBN 978-0-444-88071-0.
延伸閱讀
- Margolius, Barbara H. Permutations with Inversions. Journal of Integer Sequences. 2001, 4.
預排序度測度
- Mannila, Heikki. Measures of presortedness and optimal sorting algorithms. IEEE Transactions on Computers. April 1985, C–34 (4): 318–325. doi:10.1109/tc.1985.5009382.
- Estivill-Castro, Vladimir; Wood, Derick. A new measure of presortedness. Information and Computation. 1989, 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3 .
- Skiena, Steven S. Encroaching lists as a measure of presortedness. BIT. 1988, 28 (4): 755–784. S2CID 33967672. doi:10.1007/bf01954897.