転倒 (数学)のソースを表示

[[File:Inversion set and vector of a permutation.svg|thumb|right|380px|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 [[w:Factorial number system|converted]] to decimal is 373.]]
[[計算機科学]]および[[離散数学]]における列の'''転倒'''（てんとう、{{lang-en-short|''inversion''}}）は、その列の項の対であって、それらの項の成分が自然な[[全順序|順番]]から外れているようなものを言う。

== 定義 ==
きちんと述べれば、<math>A=(A_1, \ldots, A_n)</math> を相異なる ''n'' 個の全順序付けられた文字（例えば、数）の成す列として、<math>i < j</math> かつ <math>A_i > A_j</math> が成り立つとき、順序対 <math>(i, j)</math> を <math>A</math> の転倒と呼ぶ{{sfn|Cormen|Leiserson|Rivest|Stein|2001|pp=39}}{{sfn|Vitter|Flajolet|1990|pp=459}}。

列の'''転倒数''' (''inversion number'') は、その整列性の測度として広く用いられる{{sfn|Barth|Mutzel|2004|pp=183}}{{sfn|Vitter|Flajolet|1990|pp=459}}。きちんと述べれば、転倒数とは、その列が持つ転倒の総数
: <math>\text{inv}(A) = \# \{(A_i,A_j) \mid i < j \text{ and } A_i > A_j\}</math>
のことを言う{{sfn|Barth|Mutzel|2004|pp=183}}。他の（事前-）整列性測度としては、その列からいくつかの項を消し去って完全に整列された列にするために必要な取り去る項数の最小値、列が含む整列された run の長さ及び総数、文字列をソートするのに必要な入れ替えの数の最小値などがある{{sfn|Mahmoud|2000|pp=284}}。標準的な[[比較ソート]]アルゴリズムは転倒数を {{math|O(''n'' log ''n'')}} で計算することができる。

列の'''転倒ベクトル''' (''inversion vector'') ''V'' は各 ''i'' = 2, …, ''n'' に対して
: <math>V_i = \# \{k \mid k < i \text{ and } A_k > A_i\}</math>
で成分が与えられる。つまり、''V'' の各成分は、もとの列の対応する項の値より大きくなる先行項の総数である。列の転倒ベクトルの成分数は、もちろん初項に先行するそれより大きくなる項などはないので、もとの列の成分数より一つ少なくなることに注意。列の各[[置換_(数学)|置換]]はただ一つの転倒ベクトルを持ち、（完全に整列された）列の任意に与えられた置換を、その列と置換の転倒ベクトルをつかって作り出すことができる{{sfn|Pemmaraju|Skiena|2003|pp=69}}。

== 置換の弱順序 ==
[[File:Permutohedron.svg|thumb|4次対称群の置換多面体]]
''n'' 文字の置換全体の成す集合に、置換の'''弱順序''' (''weak order'') と呼ばれる[[半順序]]の構造を入れることができて、[[束 (束論)|束]]が得られる。

この順序を定義するために、使う文字は 1 から ''n'' までの整数とし、Inv(''u'') は整数の間の自然な順序に対する置換 ''u'' の転倒集合とする。つまり、Inv(''u'') は 1 ≤ ''i'' &lt; ''j'' ≤ ''n'' かつ ''u''(''i'') &gt; ''u''(''j'') となるような順序対 (''i'', ''j'') 全体の成す集合である。このとき、弱順序に関して ''u'' ≤ ''v'' となることを、Inv(''u'') ⊆ Inv(''v'') を以って定義する。

この弱順序の[[ハッセ図]]の辺は、''u'' &lt; ''v'' かつ ''v'' は ''u'' から隣接した二つの値を入れ替えることによって得られるような置換の組 ''u'', ''v'' で与えられる。これらの辺全体は、[[置換多面体]]の[[骨格 (位相幾何学)|骨格]]に同型な[[置換群]]の[[ケイリーグラフ]]を成す。

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

== 関連項目 ==
* [[ルービックキューブ]]
<!--
{{commons|Category:Inversion (discrete mathematics)|Inversion (discrete mathematics)}}
* [[Factorial number system]] (a factorial number is a reflected inversion vector)
* [[Permutation group#Transpositions, simple transpositions, inversions and sorting|Transpositions, simple transpositions, inversions and sorting]]
* [[Damerau–Levenshtein distance]]
* {{仮リンク|置換の偶奇性|en|Parity of a permutation}}

'''Sequences in the [[On-Line Encyclopedia of Integer Sequences|OEIS]]:'''
* [https://oeis.org/wiki/Index_to_OEIS:_Section_Fa#factorial Index entries for sequences related to factorial numbers]
* Reflected inversion vectors: {{OEIS link|A007623}} and {{OEIS link|A108731}}
* Sum of inversion vectors, cardinality of inversion sets: {{OEIS link|A034968}}
* Inversion sets of finite permutations interpreted as binary numbers: {{OEIS link|A211362}} &nbsp; (related permutation: {{OEIS link|A211363}})
* Finite permutations that have only 0s and 1s in their inversion vectors: {{OEIS link|A059590}} &nbsp; (their inversion sets: {{OEIS link|A211364}})
* Numbers of permutations of n elements with k inversions; Mahonian numbers: {{OEIS link|A008302}} &nbsp; (their row maxima; Kendall-Mann numbers: {{OEIS link|A000140}})
* Number of connected labeled graphs with n edges and n nodes: {{OEIS link|A057500}}
* Arrays of permutations with similar inversion sets and inversion vectors: {{OEIS link|A211365}}, {{OEIS link|A211366}}, {{OEIS link|A211367}}, {{OEIS link|A211368}}, {{OEIS link|A211369}}, {{OEIS link|A100630}}, {{OEIS link|A211370}}, {{OEIS link|A051683}}
-->

== 参考文献 ==
{{reflist|refs=}}

=== 出典 ===
{{refbegin|1}}
* {{cite journal|ref=harv|first1=Wilhelm|last1=Barth|first2=Petra|last2=Mutzel|title=Simple and Efficient Bilayer Cross Counting|journal=[[Journal of Graph Algorithms and Applications]]|volume=8|issue=2|pages=179&ndash;194|year=2004}}
* {{cite book|ref=harv
 | first1=Thomas H.|last1=Cormen|authorlink1=Thomas H. Cormen
 | last2=Leiserson|first2=Charles E.|authorlink2=Charles E. Leiserson
 | last3=Rivest|first3=Ronald L.|authorlink3=Ron Rivest
 | last4=Stein|first4=Clifford|authorlink4=Clifford Stein
 | title = [[Introduction to Algorithms]]
 | publisher = MIT Press and McGraw-Hill
 | year = 2001
 | isbn = 0-262-53196-8
 | edition = 2nd
 }}
* {{cite book|ref=harv|title=Sorting: a distribution theory|chapter=Sorting Nonrandom Data|volume=54|series=Wiley-Interscience series in discrete mathematics and optimization|first=Hosam Mahmoud|last=Mahmoud|publisher=Wiley-IEEE|year=2000|isbn10=0471327107|isbn=978-0-471-32710-3}}
* {{cite book|ref=harv|title=Computational discrete mathematics: combinatorics and graph theory with Mathematica|chapter=Permutations and combinations|first1=Sriram V.|last1=Pemmaraju|first2=Steven S.|last2=Skiena|publisher=Cambridge University Press|year=2003|isbn10=0521806860|isbn=978-0-521-80686-2}}
* {{cite book|ref=harv|title=Algorithms and Complexity|volume=1|editor1-first=Jan|editor1-last=van Leeuwen|editor1-link=Jan van Leeuwen|edition=2nd|publisher=Elsevier|year=1990|isbn10=0444880712|isbn=978-0-444-88071-0|chapter=Average-Case Analysis of Algorithms and Data Structures|first1=J.S.|last1=Vitter|first2=Ph.|last2=Flajolet}}
{{refend}}

=== 関連文献 ===
* {{cite journal|ref=harv|journal=Journal of Integer Sequences|volume=4|year=2001|title=Permutations with Inversions|first=Barbara H.|last=Margolius}}

=== 事前整列性測度 ===
* {{cite journal|ref=harv|journal=Lecture Notes in Computer Science|year=1984|volume=172|pages=324&ndash;336|doi=10.1007/3-540-13345-3_29|title=Measures of presortedness and optimal sorting algorithms|first=Heikki|last=Mannila|authorlink=Heikki Mannila}}
* {{cite journal|ref=harv|first1=Vladimir|last1=Estivill-Castro|first2=Derick|last2=Wood|title=A new measure of presortedness|journal=Information and Computation|volume=83|issue=1|pages=111&ndash;119|year=1989}}
* {{cite journal|ref=harv|first=Steven S.|last=Skiena|year=1988|title=Encroaching lists as a measure of presortedness|journal=BIT|volume=28|issue=4|pages=755&ndash;784}}

{{DEFAULTSORT:てんとう}}
[[Category:置換]]
[[Category:順序集合論]]
[[Category:文字列の類似度]]
[[Category:ソート]]
[[Category:組合せ論]]
[[Category:数学に関する記事]]