逆序对
此条目需要精通或熟悉相关主题的编者参与及协助编辑。 (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.