[[転倒数]]

転倒数

具体的な例でイメージすると、$\{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,\ldots,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を用意する。最大値がわかっていることが前提だが、だいたいは制約条件がある。

数列を先頭から順番に処理する

$i$ 番目(1-indexed)の項を $p_i$ とする。各項に付き、以下の2つの処理を行う。

BITに加算する

$ADD(p_i, 1)$(BITの $p_i$ の位置に、1を加算する)

自分より左にある自分より大きい数の個数を求める

先頭から順番に処理しているので、今BITにあるのは「自分より左に各数がいくつあるか」の情報である。

自分より左で $p_i$ 以下の数の個数は、$SUM(p_i)$(BITで $1$~$p_i$ の和)を求めることで得られる。

逆に言うと、$p_i$ より大きい数の個数は、$i - SUM(p_i)$ である。

数列の各要素につきこれを足し合わせることで、転倒数が得られる。


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):
    bit.add(p, 1)
    ans += i + 1 - sum(p)

print(ans)

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