Pythonでマージソートの再帰呼び出しがちょうどk回になる配列を見つける方法

問題の概要

2つの整数 a と b が与えられたとき、[1, a] の範囲の値をすべて含み、再帰的なマージソート関数がちょうど b 回呼び出されるような配列を見つけることを考えます。

例えば、入力が a = 10、b = 15 の場合、出力は次のようになります。

[3, 1, 4, 6, 2, 8, 5, 9, 10, 7]

解法のアプローチ

この問題は、再帰関数を使って配列を構築しながら、要素の入れ替えによってマージソートの呼び出し回数を調整することで解けます。手順は以下の通りです。

• 再帰関数 solve(left, right, array, b) を定義します。
• b < 1 または区間の幅が1（left + 1 == right）の場合は、それ以上処理せずに return します。
• b を 2 減らします（b := b − 2）。
• 中央位置 mid := (left + right) // 2 を求めます。
• array[mid − 1] と array[mid] の値を入れ替えます。
• solve(left, mid, array, b) と solve(mid, right, array, b) を再帰的に呼び出します。

メインの関数では次のように処理します。

• b が偶数の場合は「None」を表示して終了します（後述の理由により、解は必ず奇数回になります）。
• サイズ a + 2 の配列を 0 で初期化し、array[0] = 1、array[i] = i + 1（i = 1 ～ a − 1）として [1, a] の値を設定します。
• b を 1 減らしてから solve(0, a, array, b) を呼び出します。
• 最後に配列とサイズ a を返します。

実装例

以下にPythonでの実装例を示します。

def solve(left, right, array, b):
    if (b < 1 or left + 1 == right):
        return
    b -= 2
    mid = (left + right) // 2
    temp = array[mid - 1]
    array[mid - 1] = array[mid]
    array[mid] = temp
    solve(left, mid, array, b)
    solve(mid, right, array, b)

def find_arr(a, b):
    if (b % 2 == 0):
        print("None")
        return
    array = [0 for i in range(a + 2)]
    array[0] = 1
    for i in range(1, a):
        array[i] = i + 1
    b -= 1
    solve(0, a, array, b)
    return array, a

a = 10
b = 15
array, size = find_arr(a, b)
print(array[:size])

入力と出力

入力：

10, 15

出力：

[3, 1, 4, 6, 2, 8, 5, 9, 10, 7]

仕組みの解説

長さ n の配列に対してマージソートを完全に実行すると、再帰呼び出しは合計 2n − 1 回発生します。n = 10 の場合は 19 回です。

このアルゴリズムでは、再帰の各段階で中央付近の隣接要素を入れ替えることで、一部の区間が早い段階で整列済みの状態になります。その結果、それ以上の分割・再帰が不要となり、1回の入れ替えにつき呼び出し回数を2回ずつ減らすことができます。

したがって、実現可能な呼び出し回数は常に奇数となります。これが、b が偶数の場合に「None」を返す理由です。a = 10、b = 15 の例では、19 回から 4 回（＝入れ替え2回分）減らしてちょうど 15 回の呼び出しを実現しています。