Inversion (discrete mathematics)

ウィキペディア

転倒 (数学)

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/23 09:34 UTC 版)

The permutation (4,1,5,2,6,3) has the inversion vector (0,1,0,2,0,3) and the inversion set {(1,2),(1,4),(3,4),(1,6),(3,6),(5,6)}.The inversion vector converted to decimal is 373.

計算機科学および離散数学における列の転倒（てんとう、英: inversion）は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。

定義

きちんと述べれば、$A=(A_{1},\ldots ,A_{n})$

4次対称群の置換多面体

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 で与えられる。これらの辺全体は、置換多面体の骨格に同型な置換群のケイリーグラフを成す。

恒等置換は弱順序に関する最小元であり、恒等置換を逆順にして得られる置換が最大元になる。

関連項目

• ルービックキューブ

参考文献

1. ^ Cormen et al. 2001, pp. 39.
2. ^ ^{a b} Vitter & Flajolet 1990, pp. 459.
3. ^ ^{a b} Barth & Mutzel 2004, pp. 183.
4. ^ Mahmoud 2000, pp. 284.
5. ^ 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.