転倒数
具体的な例でイメージすると、$(3,10,1,8,5)$ のような数列を昇順にソートする時、「正しい順序になっていないペアの数」のことである。
これは、隣り合う2数の交換を繰り返すことでソートするバブルソートにおいて、その必要な最小回数と一致する。
例の場合、$(3,1)(10,1)(10,8)(10,5)(8,5)$ の5つの組で、左にある数字が右より大きくなっているので、転倒数は5である。
実際にやってみると、
3 10 1 8 5
×
3 1 10 8 5
×
3 1 8 10 5
×
3 1 8 5 10
×
1 3 8 5 10
×
1 3 5 8 10
たしかに5回で並び替えられる。
転倒数の求め方
数列の各要素について、独立に考えることが出来る。
つまり、「自分より右にある、自分より小さな数の個数」を全要素求めて足し合わせると、それが転倒数となる。
3→ 10 1 8 5 : 1 の 1つ
10→ 1 8 5 : 1,8,5 の 3つ
1→ 8 5 : なし
8→ 5 : 5 の 1つ
5→ : なし
1+3+1 = 5
また、「自分より左にある、自分より大きな数の個数」でも同じ。
3 10 1 8 ←5 : 10,8 の 2つ 3 10 1 ←8 : 10 の 1つ 3 10 ←1 : 3,10 の 2つ 3 ←10 : なし ←3 : なし
「自分より左にある、自分より大きな数の個数」を高速に求めるには、 Binary Indexed Tree を用いる方法が使われる。
BITの詳細は上記リンクを参照。以下の処理を高速に行うデータ構造だ。
- 数列 $(a_1,a_2,...,a_n)$ があり、最初、全ての要素は $0$ である
- 以下の2つの要求を処理する
ADD(i, x): $a_i$ に $x$ を加算（$1 \le i \le n$）SUM(t): $a_1$ から $a_t$ までの合計を得る（$1 \le t \le n$）
これを用いて、以下のように算出する。
BITを用意
まず、数列の最大値以上のサイズのBITを用意する。
最大値がわかっている必要がある。
以下のような場合は、事前に圧縮する。
- 負の数や、小数を含む
- 続く実装では、数列の各要素をBIT上のindexに対応づけるので、非負整数である必要がある
- 最大値が巨大すぎる
- 同じ理由で、時間的・メモリ的に無理
圧縮とは、数列の要素を事前に小さい順に $0,1,2,3,...$ に対応づけて置き換えることを指す。
すると数列の長さ $N$ が、最大値の上限となる。
転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。
A = [ 1000 -5 1001 1000 -1000 ] ↓ A'= [ 2 1 3 2 0 ]
数列を先頭から順番に処理する
$i$ 番目（0-indexed）の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。
自分より左にある自分より大きい数の個数を求める
先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。
その個数の総和は $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)$
class Bit:
def __init__(self, n):
self.size = n
self.tree = [0] * (n + 1)
def sum(self, i):
s = 0
while i > 0:
s += self.tree[i]
i -= i & -i
return s
def add(self, i, x):
while i <= self.size:
self.tree[i] += x
i += i & -i
ppp = [3, 10, 1, 8, 5]
bit = Bit(16)
ans = 0
for i, p in enumerate(ppp):
ans += i - sum(p)
bit.add(p, 1)
print(ans)
末尾からでもよい
数列を末尾から処理してもよい。（$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,...$ と番号を振り、これに対応するようにソート前も置き換える。
i a m l o r d v o l d e m o r t 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 t 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$ の並びから必ず一意に決まる」という法則がある。
前 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$ に左から順番に合わせるようシミュレーションしていけば、より少ない計算量で偶奇は分かるんだけどね。転倒数ライブラリを持っていれば使えるというだけ。
