[[転倒数]]

差分

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

この比較画面へのリンク

両方とも前のリビジョン前のリビジョン
次のリビジョン
前のリビジョン
programming_algorithm:dynamic_programming:inversion [2018/09/24] – [転倒数] ikatakosprogramming_algorithm:dynamic_programming:inversion [2023/04/05] (現在) – [swap回数(互換)の偶奇] ikatakos
行 3: 行 3:
   * [[wpjp>転倒 (数学)]]   * [[wpjp>転倒 (数学)]]
  
-具体的な例でイメージすると、$\{3,10,1,8,5\}$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。+具体的な例でイメージすると、$(3,10,1,8,5)$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。
  
 これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。 これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。
行 29: 行 29:
 数列の各要素について、独立に考えることが出来る。 数列の各要素について、独立に考えることが出来る。
  
-つまり、「自分より右にある、自分より小さな数の個数」を全要素求めて足し合わせると、それが転倒数となる。+つまり、「自分より右にある、自分より小さな数の個数」を全要素求めて足し合わせると、それが転倒数となる。
  
     3→ 10         : 1     の 1つ     3→ 10         : 1     の 1つ
行 38: 行 38:
                             1+3+1 = 5                             1+3+1 = 5
  
-また、「自分より左にある、自分より大きな数の個数」でも同じ事である+また、「自分より左にある、自分より大きな数の個数」でも同じ。
  
     3   10     8 ←5   : 10,8 の 2つ     3   10     8 ←5   : 10,8 の 2つ
行 49: 行 49:
 [[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] を用いる方法が使われる。 [[programming_algorithm:data_structure:binary_indexed_tree|Binary Indexed Tree]] を用いる方法が使われる。
  
-BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造である+BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造
  
-  * 数列$\{a_1,a_2,...,a_n\}$があり、最初、全ての要素は0である+  * 数列 $(a_1,a_2,...,a_n)$ があり、最初、全ての要素は $0である
   * 以下の2つの要求を処理する   * 以下の2つの要求を処理する
-    * ''ADD(i, x)'': $a_i$に$x$を加算($1 \le i \le n$) +    * ''ADD(i, x)'': $a_i$ に $x$ を加算($1 \le i \le n$) 
-    * ''SUM(t)'': $a_1$から$a_t$までの合計を得る($1 \le t \le n$)+    * ''SUM(t)'': $a_1$ から $a_t$ までの合計を得る($1 \le t \le n$)
  
 これを用いて、以下のように算出する。 これを用いて、以下のように算出する。
  
 ===BITを用意=== ===BITを用意===
-まず、数列の最大値以上のサイズのBITを用意する。最大値がわかっていることが前提だがだいたい制約条件がある。+ 
 +まず、数列の最大値以上のサイズのBITを用意する。 
 + 
 +最大値がわかっている必要ある。 
 + 
 +以下のような場合は、事に圧縮する。 
 + 
 +  * 負の数や小数を含む 
 +    * 続く実装で、数列の各要素をBIT上のindexに対応づけるので、非負整数である必要がある 
 +  * 最大値が巨大すぎる 
 +    * 同じ理由で、時間的・メモリ的に無理 
 + 
 +圧縮とは、数列の要素を事前に小さい順に $0,1,2,3,...$ に対応づけて置き換えることを指す。\\ 
 +すると数列の長さ $N$ が、最大値の上限となる。\\ 
 +転倒数では大小関係しか見ないので、圧縮しても結果は変わらない 
 + 
 +  A = [ 1000    -5  1001  1000 -1000 ] 
 +   ↓ 
 +  A'= [    2                 0 ] 
  
 ===数列を先頭から順番に処理する=== ===数列を先頭から順番に処理する===
-$i$ 番目(1-indexed)の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。 
  
-==BITに加算する== +$i番目0-indexed)項を $p_i$ とする。各項付き以下の2つの処理行う。
-$ADD(p_i, 1)$(BITの $p_i$ の位置に、1加算する)+
  
 ==自分より左にある自分より大きい数の個数を求める== ==自分より左にある自分より大きい数の個数を求める==
-先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。 
  
-自分より左で $p_i$ 以下の数の個数は$SUM(p_i)$(BITで $1$~$p_i$ の和)を求めることで得られる。+先頭から順番に処理しているので、今BITにあるのは「自分より左に各がいくつあるか」の情報である。\\ 
 +の個数の総和は $i$ でる。
  
-逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。+自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$($p_1~p_i$ の和)を求めることで得られる。 
 + 
 +逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ となる。
  
 数列の各要素につきこれを足し合わせることで、転倒数が得られる。 数列の各要素につきこれを足し合わせることで、転倒数が得られる。
 +
 +==BITに加算する==
 +
 +$i+1$ 以降のために、BITの $p_i$ の位置に $1$ を加算する
 +
 +  * $ADD(p_i, 1)$
  
 <sxh python> <sxh python>
行 100: 行 125:
  
 for i, p in enumerate(ppp): for i, p in enumerate(ppp):
 +    ans += i - sum(p)
     bit.add(p, 1)     bit.add(p, 1)
-    ans += i + 1 - sum(p) 
  
 print(ans) print(ans)
 </sxh> </sxh>
 +
 +=== 末尾からでもよい ===
 +
 +数列を末尾から処理してもよい。($i=N-1,N-2,...,0$ の順)
 +
 +その場合、各 $i$ における $SUM(p_i-1)$ で「自身より右にある、自身より小さい値の個数」を直で得られるので、$i$ から引くというプロセスが省け、人によっては多少わかりやすいかもしれない。ただしSUMの引数は $p_i-1$ にする必要がある。
 +
 +
 +===== バリエーション =====
 +
 +==== 同じ要素を含む場合 ====
 +
 +転倒の定義が「$i \lt j$ なのに $A_i \gt A_j$ となっている $(i,j)$ ペア」なので、
 +転倒数に $A_i=A_j$ のペアは含まない。
 +
 +バブルソートの交換回数においても、同じ要素は交換しても状況が何も変わらないので行う必要は無く、最小回数には入らない。
 +
 +つまり、(転倒数自体とは関係ない話題だが)ソートする前と後とで同じ要素内の順番は変わらない。
 +
 +  ソート前  1 4 1 4 2 1 3 5 6
 +            | ,-'     |
 +            | | ,-----'
 +            v v v
 +  ソート後  1 1 1 2 3 4 4 5 6
 +
 +転倒数を求める上では、(同じ数字を含まない場合でも変わらないが、今一度)境界に注意。
 +
 +上記の、先頭から見ていく実装例で、必要なのは「自身__より大きい__、自身より左に出現済みの数の個数」なので、
 +$i$ から引くのは「自身__以下の__、自身より左に出現済みの数の個数」である。
 +
 +
 +==== 文字列 ====
 +
 +''tom marvolo riddle'' を ''i am lord voldemort'' に、(空白は無視して)隣接する文字の交換だけで並べ替える最小手数。
 +
 +これも転倒数に言い換えられる。
 +
 +ソート後の文字列の左から出てくる順に $1,2,3,...$ と番号を振り、これに対応するようにソート前も置き換える。
 +
 +    a  m  l  o  r  d  v  o  l  d  e  m  o  r  t
 +    2  3  4  5  6  7  8  9 10 11 12 13 14 15 16
 +  
 +    o  m  m  a  r  v  o  l  o  r  i  d  d  l  e
 +  16  5  3 13  2  6  8  9  4 14 15  1  7 11 10 12  ←これの転倒数を求めればよい
 +
 +「同じ要素を含む場合」で述べたように、ソート前後で同じ要素内の順番は変わらないので、同じ文字同士は「これは何個目の"m"か」みたいなのを注意して置き換える。
 +
 +
 +==== 先読み不可 ====
 +
 +数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、
 +
 +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
 +  
 +      3 1 4 2 5
 +      v       v
 +  1回 5 1 4 2 3
 +        v v
 +  2回 5 4 1 2 3
 +          v v
 +  3回 5 4 2 1 3
 +            v v
 +  4回 5 4 2 3 1  4回で並び替えられた。他の手順でも、絶対に偶数回になる
 +
 +これは、例えば「swapを2回まとめて行うことに相当する操作を"1回"とするような操作だけを使って、数列 $A$ を $B$ にできますか?」
 +の判定問題の、可能・不可能の証明に使えることがある。(奇数回のswapが必要なら不可能)
 +
 +で、実際に偶数なのか奇数なのか? を判定したいときに転倒数を使える。\\
 +__転倒数の偶奇が一致すれば偶数回(偶置換)、不一致なら奇数回(奇置換)__となる。
 +
 +これは、任意の2つをswapする操作によって、転倒数は必ず奇数しか変化しないことで言える。
 +
 +  ... 3 x x x 7 ...
 +      ↓
 +  ... 7 x x x 3 ...
 +  
 +  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$ に左から順番に合わせるようシミュレーションしていけば、より少ない計算量で偶奇は分かるんだけどね。転倒数ライブラリを持っていれば使えるというだけ。
 +
programming_algorithm/dynamic_programming/inversion.1537753043.txt.gz · 最終更新: 2018/09/24 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0