[[転倒数]]

転倒数

具体的な例でイメージすると、$(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 riddlei 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の代わりに平衡二分探索木等を使うと、値の上限を気にせずここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。

programming_algorithm/dynamic_programming/inversion.txt · 最終更新: 2022/08/22 by ikatakos
CC Attribution 4.0 International
Driven by DokuWiki Recent changes RSS feed Valid CSS Valid XHTML 1.0