転倒 (数学)
n 文字の置換全体の成す集合に、置換の弱順序 (weak order) と呼ばれる半順序の構造を入れることができて、束が得られる。
この順序を定義するために、使う文字は 1 から n までの整数とし、Inv(u) は整数の間の自然な順序に対する置換 u の転倒集合とする。つまり、Inv(u) は 1 ≤ i < j ≤ n かつ u(i) > u(j) となるような順序対 (i, j) 全体の成す集合である。このとき、弱順序に関して u ≤ v となることを、Inv(u) ⊆ Inv(v) を以って定義する。
この弱順序のハッセ図の辺は、u < v かつ v は u から隣接した二つの値を入れ替えることによって得られるような置換の組 u, v で与えられる。これらの辺全体は、置換多面体の骨格に同型な置換群のケイリーグラフを成す。
恒等置換は弱順序に関する最小元であり、恒等置換を逆順にして得られる置換が最大元になる。
関連項目
参考文献
- ^ Cormen et al. 2001, pp. 39.
- ^ a b Vitter & Flajolet 1990, pp. 459.
- ^ a b Barth & Mutzel 2004, pp. 183.
- ^ Mahmoud 2000, pp. 284.
- ^ Pemmaraju & Skiena 2003, pp. 69.
出典
- Barth, Wilhelm; Mutzel, Petra (2004). “Simple and Efficient Bilayer Cross Counting”. Journal of Graph Algorithms and Applications 8 (2): 179–194.
- Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001). Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-53196-8
- Mahmoud, Hosam Mahmoud (2000). “Sorting Nonrandom Data”. Sorting: a distribution theory. Wiley-Interscience series in discrete mathematics and optimization. 54. Wiley-IEEE. ISBN 978-0-471-32710-3
- Pemmaraju, Sriram V.; Skiena, Steven S. (2003). “Permutations and combinations”. Computational discrete mathematics: combinatorics and graph theory with Mathematica. Cambridge University Press. ISBN 978-0-521-80686-2
- Vitter, J.S.; Flajolet, Ph. (1990). “Average-Case Analysis of Algorithms and Data Structures”. In van Leeuwen, Jan. Algorithms and Complexity. 1 (2nd ed.). Elsevier. ISBN 978-0-444-88071-0
関連文献
- Margolius, Barbara H. (2001). “Permutations with Inversions”. Journal of Integer Sequences 4.
事前整列性測度
- Mannila, Heikki (1984). “Measures of presortedness and optimal sorting algorithms”. Lecture Notes in Computer Science 172: 324–336. doi:10.1007/3-540-13345-3_29.
- Estivill-Castro, Vladimir; Wood, Derick (1989). “A new measure of presortedness”. Information and Computation 83 (1): 111–119.
- Skiena, Steven S. (1988). “Encroaching lists as a measure of presortedness”. BIT 28 (4): 755–784.
- 転倒数のページへのリンク