転倒数

転倒 (数学)

具体的な例でイメージすると、$(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における計算に時間がかかってしまう。
そのような場合は、数列の要素を事前に小さい順に $1,2,3,...$ に対応づけて圧縮してもよい。
すると数列の長さ $N$ が最大値の上限となる。
転倒数では大小関係しか見ないので、圧縮しても結果は変わらない。

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

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

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

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

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

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

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

BITに加算する

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 \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

今一度、境界に注意。

上記の左から見ていく実装例で、必要なのは「自身より大きい、自身より左に出現済みの数の個数」なので、全体から引くのは「自身以下の、自身より左に出現済みの数の個数」である。

文字列

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”か」みたいなのを注意して置き換える。

先読み不可

数列の最大値もわからないし、先読みもできないので圧縮もできない、みたいな変な状況がもしあったら、、、

平衡二分探索木等を使うと、ここまでに出てきた数のうち自身が何番目に小さいかを取得できるので、代用できるはず。

目次

転倒数