逆順列（離散数学）

逆順列の1つが強調表示された順列。逆順列は、位のペア（2, 4）または元のペア（5, 2）で表されます。この順列の逆順列は、元に基づく表記法では、(3, 1)、(3, 2)、(5, 1)、(5, 2)、(5, 4)です

コンピュータサイエンスと離散数学において、シーケンス内の反転とは、自然な順序から外れた要素のペアのことです。

定義

反転

を順列とする。との場合、との間には反転が存在する。反転は、位[ 1 ] [ ^{2 ]または元[ 3} ] ^{[ 4 ] [ 5 ]のいずれか}を含む順序付きペアで示される${\displaystyle \pi}$ ${\displaystyle \pi}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle i<j}$ ${\displaystyle \pi (i)>\pi (j)}$ ${\displaystyle (i,j)}$ ${\displaystyle {\bigl (}\pi (i),\pi (j){\bigr )}}$

反転集合は、すべての反転の集合である。位置ベース表記を用いた順列の反転集合は、要素ベース表記を用いた逆順列の反転集合において、各順序対の2つの要素を交換したものと同じである。同様に、要素ベース表記を用いた順列の反転集合は、位置ベース表記を用いた逆順列の反転集合において、各順序対の2つの要素を交換したものと同じである。^{[ 6 ]}

反転は通常順列に対して定義されますが、列に対しても定義できます。を列（または多重集合順列^{[ 7 ]} ）とします。 かつ のとき、位置のペア^{[ 7 ] [ 8 ]}または要素のペア^{[ 9 ]}のいずれかを の反転と呼びます。 ${\displaystyle S}$ ${\displaystyle i<j}$ ${\displaystyle S(i)>S(j)}$ ${\displaystyle (i,j)}$ ${\displaystyle {\bigl (}S(i),S(j){\bigr )}}$ ${\displaystyle S}$

シーケンスの場合、異なる場所のペアが同じ値のペアを持つ可能性があるため、要素ベースの定義による反転は一意ではありません。

反転数

数列の反転数^{[ 10 ]}は、反転集合の濃度です。これは、順列^{[ 5 ]}または数列^{[ 9 ]}のソート度（事前ソート度と呼ばれることもあります）の一般的な尺度です。反転数は0から0までの範囲です。順列とその逆は、同じ反転数を持ちます ${\displaystyle {\mathtt {inv}}(X)}$ ${\displaystyle X=\langle x_{1},\dots,x_{n}\rangle}$ ${\displaystyle {\frac {n(n-1)}{2}}}$

例えば、列は順序付けられているためです。また、が偶数の場合（各ペアが反転であるため）、この最後の例は、直感的に「ほぼソートされている」集合でも、反転の数が2乗個存在する可能性があることを示しています。 ${\displaystyle {\mathtt {inv}}(\langle 1,2,\dots ,n\rangle )=0}$ ${\displaystyle n=2m}$ ${\displaystyle {\mathtt {inv}}(\langle m+1,m+2,\dots,2m,1,2,\dots,m\rangle)=m^{2}}$ ${\displaystyle (1\leq i\leq m<j\leq 2m)}$

反転数とは、順列の矢印図における交差の数、^{[ 6 ]、}恒等順列から の順列のケンドールタウ距離、および以下に定義される各反転関連ベクトルの合計である。

ソート度の他の尺度としては、完全にソートされたシーケンスを得るためにシーケンスから削除できる要素の最小数、シーケンス内のソートされた「連続」の数と長さ、スピアマンのフットルール（各要素のソート位置からの距離の合計）、シーケンスをソートするために必要な交換の最小数などがある。^{[ 11 ]}標準的な比較ソートアルゴリズムは、O( n log n )の時間で反転数を計算するように適応できる。^{[ 12 ]}

反転関連ベクトル

順列の反転を、それを一意に決定するベクトルに凝縮する、3つの類似ベクトルが使用されています。これらは、反転ベクトルまたはレーマーコードと呼ばれることがよくあります。（出典のリストはここにあります。）

この記事では、 Wolfram ^{[ 13 ]}と同様に、反転ベクトル（）という用語を使用します。残りの2つのベクトルは、左反転ベクトルと右反転ベクトルと呼ばれることもありますが、反転ベクトルとの混同を避けるため、この記事では左反転カウント（）と右反転カウント（ ）と呼びます 。階乗として解釈すると、左反転カウントは逆辞書式順列を与え、^{[ 14 ]}右反転カウントは辞書式インデックスを与えます。 ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle r}$

ローテ図

反転ベクトル：${\displaystyle v}$ 元に基づく定義では、小さい方（右）の成分がである反転の数です。^{[ 3 ]}${\displaystyle v(i)}$ ${\displaystyle i}$

${\displaystyle v(i)}$ は、 内の要素数が以前より大きくなります。${\displaystyle \pi}$ ${\displaystyle i}$ ${\displaystyle i}$

${\displaystyle v(i)~~=~~\#\{k\mid k>i~\land ~\pi ^{-1}(k)<\pi ^{-1}(i)\}}$

左反転数:${\displaystyle l}$ 場所ベースの定義では、 は、大きい方(右)の要素が である反転の数です。 ${\displaystyle l(i)}$ ${\displaystyle i}$

${\displaystyle l(i)}$ は、 内の要素数が以前より大きくなります。${\displaystyle \pi}$ ${\displaystyle \pi (i)}$ ${\displaystyle \pi (i)}$

${\displaystyle l(i)~~=~~\#\left\{k\mid k<i~\land ~\pi (k)>\pi (i)\right\}}$

右反転カウント、Lehmer コードとも呼ばれます。${\displaystyle r}$ 場所ベースの定義では、 は小さい方(左) の要素が である反転の数です。 ${\displaystyle r(i)}$ ${\displaystyle i}$

${\displaystyle r(i)}$ の要素数はより後の方が小さいです。${\displaystyle \pi}$ ${\displaystyle \pi (i)}$ ${\displaystyle \pi (i)}$

${\displaystyle r(i)~~=~~\#\{k\mid k>i~\land ~\pi (k)<\pi (i)\}}$

と はどちらも、ローテ図を用いて見つけることができます。ローテ図は、1 を点で表し、その右と下に点があるすべての位置に反転（多くの場合、十字で表されます）を持つ順列行列です。 はローテ図の行 における反転の合計であり、 は 列 における反転の合計です。逆順列の順列行列は転置 であるため、順列の はその逆順列の であり、その逆も同様です。 ${\displaystyle v}$ ${\displaystyle r}$ ${\displaystyle r(i)}$ ${\displaystyle i}$ ${\displaystyle v(i)}$ ${\displaystyle i}$ ${\displaystyle v}$ ${\displaystyle r}$

例: 4つの要素のすべての順列

4要素順列の6つの可能な反転

以下のソート可能な表は、4つの要素（列）の24通りの順列と、それらの位置に基づく反転集合（pb列）、反転関連ベクトル（列、、列）、および反転番号（#列）を示しています。（小さな活字で見出しのない列は、隣の列を反映しており、コレクシコグラフィック順にソートするために使用できます。） ${\displaystyle \pi}$ ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle r}$

と は常に同じ数字を持ち、 とはどちらも位置に基づく反転集合に関連していることがわかります。 の非自明な元は、示されている三角形の下降対角線の和であり、 の非自明な元は昇順対角線の和です。（下降対角線のペアは右成分 2、3、4 を共有し、昇順対角線のペアは左成分 1、2、3 を共有します。） ${\displaystyle v}$ ${\displaystyle l}$ ${\displaystyle l}$ ${\displaystyle r}$ ${\displaystyle l}$ ${\displaystyle r}$

テーブルのデフォルトの順序は、逆 colex order by です。これは colex order by と同じです。lex order by はlex order by と同じです。 ${\displaystyle \pi}$ ${\displaystyle l}$ ${\displaystyle \pi}$ ${\displaystyle r}$

比較のための3要素順列
0 1 2 3 4 5 ${\displaystyle \pi}$ ${\displaystyle v}$ ${\displaystyle l}$ pb ${\displaystyle r}$ # 0 123 321 00 0 0 00 00 0 0 00 00 0 0 00 0 1 213 312 10 0 0 01 01 0 0 10 10 0 0 01 1 2 132 231 01 0 0 10 10 0 0 01 01 0 0 10 1 3 312 213 11 0 0 11 11 0 0 11 20 0 0 02 2 4 231 132 20 0 0 02 20 0 0 02 11 0 0 11 2 5 321 123 21 0 0 12 21 0 0 12 21 0 0 12 3

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

${\displaystyle \pi}$ ${\displaystyle v}$ ${\displaystyle l}$ pb ${\displaystyle r}$ # 0 1234 4321 000 0 0 000 000 0 0 000 000 0 0 000 0 1 2134 4312 100 0 0 001 001 0 0 100 100 0 0 001 1 2 1324 4231 010 0 0 010 010 0 0 010 010 0 0 010 1 3 3124 4213 110 0 0 011 011 0 0 110 200 0 0 002 2 4 2314 4132 200 0 0 002 020 0 0 020 110 0 0 011 2 5 3214 4123 210 0 0 012 021 0 0 120 210 0 0 012 3 6 1243 3421 001 0 0 100 100 0 0 001 001 0 0 100 1 7 2143 3412 101 0 0 101 101 0 0 101 101 0 0 101 2 8 1423 3241 011 0 0 110 110 0 0 011 020 0 0 020 2 9 4123 3214 111 0 0 111 111 0 0 111 300 0 0 003 3 10 2413 3142 201 0 0 102 120 0 0 021 120 0 0 021 3 11 4213 3124 211 0 0 112 121 0 0 121 310 0 0 013 4 12 1342 2431 020 0 0 020 200 0 0 002 011 0 0 110 2 13 3142 2413 120 0 0 021 201 0 0 102 201 0 0 102 3 14 1432 2341 021 0 0 120 210 0 0 012 021 0 0 120 3 15 4132 2314 121 0 0 121 211 0 0 112 301 0 0 103 4 16 3412 2143 220 0 0 022 220 0 0 022 220 0 0 022 4 17 4312 2134 221 0 0 122 221 0 0 122 320 0 0 023 5 18 2341 1432 300 0 0 003 300 0 0 003 111 0 0 111 3 19 3241 1423 310 0 0 013 301 0 0 103 211 0 0 112 4 20 2431 1342 301 0 0 103 310 0 0 013 121 0 0 121 4 21 4231 1324 311 0 0 113 311 0 0 113 311 0 0 113 5 22 3421 1243 320 0 0 023 320 0 0 023 221 0 0 122 5 23 4321 1234 321 0 0 123 321 0 0 123 321 0 0 123 6

順列の弱い順序

対称群S ₄のパーミュトヘドロン

n個の項目の順列の集合には、順列の弱順序と呼ばれる半順序の構造を与えることができ、格子を形成します。

部分集合関係によって順序付けられた反転集合のハッセ図は、パーミュトヘドロンの骨格を形成します。

場所に基づく定義を用いて各反転集合に順列を割り当てると、順列の順序はパーミュトヘドロン（permutohedron）の順序となる。パーミュトヘドロンでは、辺は連続する値を持つ2つの要素の入れ替えに対応する。これは順列の弱順序である。単位元は最小値であり、単位元を反転させた順列は最大値である。

元に基づく定義を用いて各反転集合に順列を割り当てた場合、結果として得られる順列の順序はケイリーグラフの順序となる。ケイリーグラフでは、辺は連続する2つの元の入れ替えに対応する。対称群のこのケイリーグラフは、その順列化面体と類似しているが、各順列がその逆順列に置き換えられている。

参照

• 階乗法
• 順列グラフ
• ダメラウ・レーベンシュタイン距離
• 順列の偶奇性

OEISのシーケンス:

• 階乗基数表現に関連するシーケンス
• 階乗数: A007623とA108731
• 反転番号: A034968
• 有限順列の反転集合を2進数として解釈する：A211362   （関連順列：A211363）
• 反転ベクトルに0と1のみを持つ有限順列：A059590   （その反転集合：A211364）
• n個の元とk 個の反転を持つ順列の数。マホーニアン数: A008302   (その行の最大値。ケンドール・マン数: A000140 )
• n個のエッジとn 個のノードを持つ接続されたラベル付きグラフの数: A057500

参考文献

1. Aigner 2007、27ページ
2. Comtet 1974、237ページ
3. クヌース 1973、11ページ。
4. Pemmaraju & Skiena 2003、69 ページ。
5. ヴィッター&フラジョレ、1990年、459ページ。
6. グラッツァー 2016、221頁。
7. ボナ 2012年、57頁。
8. コーメンら。 2001 年、39 ページ。
9. バース＆ミュッツェル 2004年、183頁。
10. マニラ 1985 .
11. マフムード 2000、284頁。
12. クラインバーグ & タルドス 2005、225 ページ。
13. Weisstein, Eric W.「反転ベクトル」MathWorldより--Wolfram Web リソース
14. 有限順列の逆コレックス順序（ OEISの配列A055089）

参考文献

• アイグナー、マーティン (2007). 「単語表現」.列挙のコース. ベルリン、ニューヨーク: シュプリンガー. ISBN 978-3642072536。
• バート、ウィルヘルム、ミュッツェル、ペトラ(2004). 「シンプルで効率的な二重層クロスカウンティング」 .グラフアルゴリズムとアプリケーションジャーナル. 8 (2): 179–194 . doi : 10.7155/ jgaa.00088
• ボナ、ミクロス(2012)。 「2.2 複数集合の順列における反転」。順列の組み合わせ論。フロリダ州ボカラトン：CRC Press。ISBN 978-1439850510。
• コンテ、ルイ (1974). 「6.4 [n] の順列の反転」.上級組合せ論；有限展開と無限展開の技法. ドルドレヒト、ボストン: D. Reidel Pub. Co. ISBN 9027704414。
• コーメン, トーマス・H. ;レイサーソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2001). 『アルゴリズム入門（第2版）』 MIT Press, McGraw-Hill. ISBN 0-262-53196-8。
• グラッツァー、ジョージ(2016). 「7-2 基本オブジェクト」.格子理論. 特別なトピックと応用. シャム、スイス: ビルクハウザー. ISBN 978-3319442358。
• クラインバーグ、ジョン、タルドス、エヴァ (2005).アルゴリズム設計. ピアソン/アディソン・ウェズリー. ISBN 0-321-29535-8。
• ドナルド・クヌース（1973年）「5.1.1 反転」『コンピュータプログラミングの芸術』アディソン・ウェズリー出版ISBN 0201896850。
• マフムード、ホサム・マフムード (2000). 「非ランダムデータのソート」.ソート：分布理論. Wiley-Interscience 離散数学と最適化シリーズ. 第54巻. Wiley-IEEE. ISBN 978-0-471-32710-3。
• ペンマラジュ, スリラム・V.、スキエナ, スティーブン・S. (2003). 「順列と組み合わせ」.計算離散数学：Mathematicaによる組合せ論とグラフ理論. ケンブリッジ大学出版局. ISBN 978-0-521-80686-2。
• Vitter, JS; Flajolet, Ph. (1990). 「アルゴリズムとデータ構造の平均ケース分析」. van Leeuwen, Jan (編).アルゴリズムと複雑性第1巻 (第2版). エルゼビア. ISBN 978-0-444-88071-0。

さらに詳しい情報

• マーゴリウス、バーバラ・H. (2001). 「Permutations with Inversions」. Journal of Integer Sequences . 4 : 24.書誌コード: 2001JIntS...4... 24M

事前ソート度の尺度

• マニラ、ヘイッキ（1985年4月）「事前ソート度の尺度と最適ソートアルゴリズム」IEEE Transactions on Computers . C-34 (4): 318– 325. doi : 10.1109/ tc.1985.5009382
• エスティビル＝カストロ、ウラジミール；ウッド、デリック(1989). 「事前分類の新しい尺度」情報と計算. 83 ( 1): 111– 119. doi : 10.1016/0890-5401(89)90050-3 .
• スキエナ, スティーブン・S. (1988). 「事前分類の尺度としての侵入リスト」. BIT . 28 (4): 755– 784. doi : 10.1007/bf01954897 . S2CID  33967672 .