転倒数とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > 転倒数の意味・解説 

転倒 (数学)

(転倒数 から転送)

出典: フリー百科事典『ウィキペディア(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)は、その列の項の対であって、それらの項の成分が自然な順番から外れているようなものを言う。

定義

きちんと述べれば、

4次対称群の置換多面体

n 文字の置換全体の成す集合に、置換の弱順序 (weak order) と呼ばれる半順序の構造を入れることができて、が得られる。

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

この弱順序のハッセ図の辺は、u < v かつ vu から隣接した二つの値を入れ替えることによって得られるような置換の組 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. 



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「転倒数」の関連用語






6
10% |||||


8
4% |||||

9
2% |||||


転倒数のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



転倒数のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアの転倒 (数学) (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS