転倒 (数学)

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

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.

定義

きちんと述べれば、$A=(A_{1},\ldots ,A_{n})$ を相異なる n 個の全順序付けられた文字（例えば、数）の成す列として、$i<j$ かつ $A_{i}>A_{j}$ が成り立つとき、順序対 $(i,j)$ を $A$ の転倒と呼ぶ。

列の転倒数 (inversion number) は、その整列性の測度として広く用いられる。きちんと述べれば、転倒数とは、その列が持つ転倒の総数

${\text{inv}}(A)=\#\{(A_{i},A_{j})\mid i<j{\text{ and }}A_{i}>A_{j}\}$

のことを言う。他の（事前-）整列性測度としては、その列からいくつかの項を消し去って完全に整列された列にするために必要な取り去る項数の最小値、列が含む整列された run の長さ及び総数、文字列をソートするのに必要な入れ替えの数の最小値などがある。標準的な比較ソートアルゴリズムは転倒数を O(n log n) で計算することができる。

列の転倒ベクトル (inversion vector) V は各 i = 2, …, n に対して

$V_{i}=\#\{k\mid k<i{\text{ and }}A_{k}>A_{i}\}$

で成分が与えられる。つまり、V の各成分は、もとの列の対応する項の値より大きくなる先行項の総数である。列の転倒ベクトルの成分数は、もちろん初項に先行するそれより大きくなる項などはないので、もとの列の成分数より一つ少なくなることに注意。列の各置換はただ一つの転倒ベクトルを持ち、（完全に整列された）列の任意に与えられた置換を、その列と置換の転倒ベクトルをつかって作り出すことができる。

置換の弱順序

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

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

関連項目

• ルービックキューブ

参考文献

出典

• 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.