差分

このページの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 ]
@@ 行 76: / 行 86: @@
 ==自分より左にある自分より大きい数の個数を求める==
-先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。
+先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。\\
+その個数の総和は $i$ である。
-自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$（$1$～$p_i$ の和）を求めることで得られる。
+自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$（$p_1～p_i$ の和）を求めることで得られる。
-逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。
+逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ となる。
 数列の各要素につきこれを足し合わせることで、転倒数が得られる。
@@ 行 86: / 行 97: @@
 ==BITに加算する==
-BITの $p_i$ の位置に、1を加算する
+$i+1$ 以降のために、BITの $p_i$ の位置に $1$ を加算する
   * $ADD(p_i, 1)$
@@ 行 119: / 行 130: @@
 print(ans)
 </sxh>
+=== 末尾からでもよい ===
+数列を末尾から処理してもよい。（$i=N-1,N-2,...,0$ の順）
+その場合、各 $i$ における $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。
@@ 行 130: / 行 147: @@
 バブルソートの交換回数においても、同じ要素は交換しても状況が何も変わらないので行う必要は無く、最小回数には入らない。
-つまり、（転倒数自体とは関係ないが）ソートする前と後とで同じ要素内の順番は変わらない。
+つまり、（転倒数自体とは関係ない話題だが）ソートする前と後とで同じ要素内の順番は変わらない。
   ソート前  1 4 1 4 2 1 3 5 6
@@ 行 138: / 行 155: @@
   ソート後  1 1 1 2 3 4 4 5 6
-今一度、境界に注意。
+転倒数を求める上では、（同じ数字を含まない場合でも変わらないが、今一度）境界に注意。
-上記の左から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、
+上記の、先頭から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、
-全体から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。
+$i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。
@@ 行 165: / 行 182: @@
 数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、
-平衡二分探索木等を使うと、ここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。
+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$ に左から順番に合わせるようシミュレーションしていけば、より少ない計算量で偶奇は分かるんだけどね。転倒数ライブラリを持っていれば使えるというだけ。