SAIGの小橋です。アルゴリズムとデータ構造連載の5日目です。

この間、反転数が関係する問題がうまく解けなくて悔しい思いをしたので、技術ブログでアルゴリズム連載企画ができたのを機に、反転数について考えてみたいと思います。

反転数の定義

数列に対して、 かつ を満たす組(i, j)の個数を、この数列の反転数(inversion number)という。

例えば、数列2, 4, 1, 3, 5の反転数を考えましょう。 とすると かつ なので（数列のインデックスは から始まるものとします）、これは条件を満たす組の1つです。が条件を満たすので、反転数は3です。

感覚的には、「数列がソートされている状態にどれくらい近いか・遠いか」を表す指標と言えるでしょう。

なお、反転数は転倒数という名前で呼ばれることもあります。

反転数と隣接互換の関係

今回知りたいのは、反転数と隣接互換によるソート回数の関係です。

先の2, 4, 1, 3, 5 という数列に対して、隣同士の要素の交換を繰り返してソートすると、2, 4, 1, 3, 5 → 2, 1, 4, 3, 5 → 2, 1, 3, 4, 5 → 1, 2, 3, 4, 5 と3回の交換でソートできます。この必要な交換回数は、実は反転数に等しい値です。分かってしまえばそれほど難しくないのですが、それほど自明でもないので少し難しいですね。今回証明を考えてみました。

補題：数列の反転数は、その数列をバブルソートでソートするときの交換回数に等しい。

証明：数列の反転数をとおく。バブルソートによる要素の交換は、逆順のものを正しい順に直す操作である。またこの交換は隣接要素間で行われるので、操作の前後の反転数を考えると、交換された要素 だけが影響を受ける。したがって、操作によって反転数は必ず1だけ減少する。また定義より、ソートされた数列の反転数は0である。したがって、なので、は交換回数に等しい。

バブルソートのアルゴリズムについてはAIZU ONLINE JUDGEのページなどをご参照ください³。

命題：数列の反転数は、その数列を隣接要素を交換することによってソートするときの最小の交換回数に等しい。

証明：1回の隣接要素の交換によって、反転数は高々1しか減少しない。したがって、最初の反転数からソート済みの状態（反転数が0）にするには、最小でも回の交換が必要である。そして補題より、バブルソートを実行すると回の交換でソートできる。以上より、最小の交換回数は回である。

なお、最小回数を達成するために、必ずしもバブルソートを使う必要はありません。例えば、「一番小さい要素を探して、1つずつ前と交換していって一番前に移動させる。次に、残りの要素の中で一番小さい要素を探して、1つずつ前と交換していって前から2番目に移動させる……」という方式でも大丈夫です。

分割統治法による反転数の求め方

さて、反転数を求める方法について考えてみましょう。

もっとも単純な方法は、全てのペアについて1つずつチェックする方法で、計算量はとなります。

これよりも高速な解法として、Binary Indexed Tree（BIT）を用いた解法があります。「プログラミングコンテストチャレンジブック [第2版]」p.162に載っているほか、転倒数[いかたこのたこつぼ] が詳しいです。計算量はです。

しかし実は、アルゴリズム関連の他の本に載っている「反転数の求め方」は、BITによるものではありません。

アルゴリズム本の大著である「アルゴリズムデザイン」で反転数の求め方があるのは、「分割統治法」の章の中です。

分割統治法……! アルゴリズムの授業では必ず習うけど、実際にはなかなか使わないやつ……!

私自身の競技プログラミングの経験を振り返っても、分割統治法を組んだ覚えはありません。この機会に書いてみましょう（分割統治法とは何か、という話は割愛します。分割統治法を使うアルゴリズムとしてはマージソートが有名なので、適宜調べてみて下さい）。

分割された小問題を統合する部分が重要ですので、この部分だけを取り出して書き直してみましょう。

数列AとBがある。AとBはソートされた長さN/2の数列である。これに対し、「AとBをつなげた数列をソートした数列Cを求めたい。同時に、a A, b B, かつ a > bとなる 組の個数も求めたい。

反転数を求める上で数列を同時にソートすることは必須ではないので、上記の問題中にソートの話が出てくるのはやや不思議です。直観的には「バラバラな順番だったら高速に求めづらいから、余計な計算量をかけずにソートできるなら同時にソートしておいた方が後でやりやすいだろう」というところでしょうか。

さて、上記の問題に対する の解法を考えます。

数列AとBのそれぞれの先頭にポインターを置き、それを右にずらしながら小さい方の数字を数列Cに加えていくことで、ソート済みの数列を得ることができます（マージソートのときと同じです）。

あとは反転数を求めれば問題は解決です。これは、Bの要素を数列Cに加えるときに、残っているAの要素数を足し上げていけば良いです（下図を参照ください）。これにより、1つずつ数えることなく、反転数を短い計算時間で求めることが可能になります。

以上を踏まえてソースコード（Python）を書いてみましょう²。

def merge_and_count(list_a, list_b):
    len_a = len(list_a)
    len_b = len(list_b)
    idx_a = 0
    idx_b = 0
    count_inversion = 0
    merged = []

    # リストの両方が空でないとき
    while idx_a < len_a and idx_b < len_b:
        if list_a[idx_a] < list_b[idx_b]:
            merged.append(list_a[idx_a])
            idx_a += 1
        else:
            merged.append(list_b[idx_b])
            idx_b += 1
            # count_inversionを、Aの残っている要素数の分だけ増やす
            count_inversion += len_a - idx_a

    # リストの一方が空になったら、他方のリストの残りを全て出力リストに加える
    if idx_a < len_a:
        merged += list_a[idx_a:]
    if idx_b < len_b:
        merged += list_b[idx_b:]

    return count_inversion, merged

def sort_and_count(lis):
    if len(lis) == 1:
        return 0, lis
    if len(lis) == 2:
        if lis[0] < lis[1]:
            return 0, lis
        else:
            return 1, [lis[1], lis[0]]
    else:
        # リストをほぼ2等分する
        half = len(lis) // 2
        list_first = lis[:half]
        list_second = lis[half:]
        inversion_first, sorted_first = sort_and_count(list_first)
        inversion_second, sorted_second = sort_and_count(list_second)
        inversion_while_merging, sorted_full = merge_and_count(sorted_first, sorted_second)

        return inversion_first + inversion_second + inversion_while_merging, sorted_full

# 例
print(sort_and_count([2, 5, 7, 13, 3, 11]))
# -> (4, [2, 3, 5, 7, 11, 13])

計算量はBITの場合と同じく、です。

なお、AとBの要素について全探索を行って組の個数を求めると計算量は となり、反転数を求める全体の計算量も となってしまいます¹。

分割統治法による反転数計算の特徴は、以下のようになります。

• メリット：BITで計算するためには1～Nの数列の並び替えでなければならないが、分割統治法ではそのような制約は無く、任意の要素の数列で使える
• デメリット：計算量としてはBITと変わらないが、再帰による関数呼び出しが発生するため、実際にかかる計算時間はBITよりも長くなる

参考文献

アルゴリズムデザイン | Jon Kleinberg, Eva Tardos

プログラミングコンテストチャレンジブック [第2版]　～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ | 秋葉拓哉, 岩田陽一, 北川宜稔