差分

このページの2つのバージョン間の差分を表示します。

--- programming_algorithm:dynamic_programming:inversion [2022/08/17] – ikatakos
+++ programming_algorithm:dynamic_programming:inversion [2023/04/05] (現在) – [swap回数（互換）の偶奇] ikatakos
@@ 行 64: / 行 64: @@
 最大値がわかっている必要がある。
-最大値が大きすぎると、数列の要素自体は疎でも、BITにおける計算に時間がかかってしまう。\\
+以下のような場合は、事前に圧縮する。
-そのような場合は、数列の要素を事前に小さい順に $1,2,3,...$ に対応づけて圧縮してもよい。\\
-すると数列の長さ $N$ が最大値の上限となる。\\
+  * 負の数や、小数を含む
+    * 続く実装では、数列の各要素をBIT上のindexに対応づけるので、非負整数である必要がある
+  * 最大値が巨大すぎる
+    * 同じ理由で、時間的・メモリ的に無理
+圧縮とは、数列の要素を事前に小さい順に $0,1,2,3,...$ に対応づけて置き換えることを指す。\\
+すると数列の長さ $N$ が、最大値の上限となる。\\
 転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。
+  A = [ 1000    -5  1001  1000 -1000 ]
+   ↓
+  A'= [    2     1     3     2     0 ]
@@ 行 120: / 行 130: @@
 print(ans)
 </sxh>
+=== 末尾からでもよい ===
+数列を末尾から処理してもよい。（$i=N-1,N-2,...,0$ の順）
+その場合、各 $i$ における $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。
@@ 行 141: / 行 157: @@
 転倒数を求める上では、（同じ数字を含まない場合でも変わらないが、今一度）境界に注意。
-上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、
+上記の、先頭から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、
 $i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。
@@ 行 168: / 行 184: @@
 BITの代わりに平衡二分探索木等を使うと、値の上限を気にせずここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。
+===== swap回数（互換）の偶奇 =====
+隣接2項間に限らず、任意の2項目をswapするような操作（互換）を考える場合においても、その回数の偶奇を求める際に転倒数が使える。
+全ての要素が互いに区別できる、ある数列があったとする。（ここでは単純に、$1,2,...,N$ の順列 $P$ を考える）\\
+これを、任意の2項目をswapする操作を繰り返すことで別の順列 $Q$ に並び替える操作を考える。
+その操作手順は様々だが、「操作回数の偶奇は、$P,Q$ の並びから必ず一意に決まる」という法則がある。
+  * [[https://manabitimes.jp/math/949|置換と偶置換・奇置換に関する基礎的なこと | 高校数学の美しい物語]]
+  * [[https://manabitimes.jp/math/1319|差積の意味と置換の符号が定義できることの証明 | 高校数学の美しい物語]]
+  前  3 1 4 2 5
+  後  5 4 2 3 1
+1 4 2 5
+      v       v
+回 5 1 4 2 3
+        v v
+回 5 4 1 2 3
+          v v
+回 5 4 2 1 3
+            v v
+回 5 4 2 3 1  4回で並び替えられた。他の手順でも、絶対に偶数回になる
+これは、例えば「swapを2回まとめて行うことに相当する操作を"1回"とするような操作だけを使って、数列 $A$ を $B$ にできますか？」
+の判定問題の、可能・不可能の証明に使えることがある。（奇数回のswapが必要なら不可能）
+で、実際に偶数なのか奇数なのか？ を判定したいときに転倒数を使える。\\
+__転倒数の偶奇が一致すれば偶数回（偶置換）、不一致なら奇数回（奇置換）__となる。
+これは、任意の2つをswapする操作によって、転倒数は必ず奇数しか変化しないことで言える。
+  ... 3 x x x 7 ...
+      ↓
+  ... 7 x x x 3 ...
+と7をswap → 転倒数に影響があるのは、ペア自身とそれに挟まれた項のみ
+  ・3と7自体      : 1増える（または減る）                     → ±1
+  ・    x < 3 の項: 3に対して減り、7に対して増える            → ±0
+  ・3 < x < 7 の項: 3に対しても7に対しても増える（または減る）→ ±2
+  ・7 < x     の項: 3に対して増え、7に対して減る              → ±0
+  ペア自身(3,7)の変化は必ず奇数
+  ある挟まれた1項とペアの片方ずつ(3,x),(7,x)の変化は合わせて必ず偶数
+  →転倒数の変化は必ず奇数
+転倒数が奇数（＝$(1,2,...,N)$ からのswap回数が奇数回）の順列同士、偶数の順列同士なら、その間の操作回数は偶数回となる。
+･･････と、ここまで書いたが、転倒数を使わなくても、$A$ を $B$ に左から順番に合わせるようシミュレーションしていけば、より少ない計算量で偶奇は分かるんだけどね。転倒数ライブラリを持っていれば使えるというだけ。