Pythonで配列のソートに必要なシャッフル回数の期待値を求めるプログラム

要素の集合 nums が与えられ、これを非減少順(昇順)に並べ替えることを考えます。ただし、ここで使うのは「ランダム化ソート」という手法です。まず配列がソート済みかどうかを確認し、まだ整列していなければランダムにシャッフルして再度チェックします。すべての要素が正しく並ぶまで、この確認とシャッフルを繰り返します。このとき必要となるシャッフル回数の期待値を求め、答えは小数点以下6桁まで表示します。この手法は俗に「ボゴソート(Bogosort)」とも呼ばれます。

例として nums = [5,2,7] の場合を見てみましょう。このときの出力は 6 になります。3つの異なる要素の並べ方(順列)は 3! = 6 通り存在し、そのうちソート済みとなる並びは1通りだけです。つまり、1回のシャッフルで成功する確率は 1/6 であり、期待シャッフル回数はその逆数の 6 となります。

• i = 1 回目でソート済み配列が得られる確率:1/6
• i = 2 回目で初めて得られる確率:(5/6) × (1/6)

一般化すると、i 回目で初めてソート済み配列が得られる確率は (5/6)^i-1 × (1/6) と表せます。これは幾何分布に従うため、期待値は成功確率 p の逆数 1/p、すなわち 6 になります。

解法のアプローチ

この問題は次の手順で解きます。

• nums がすでにソート済みなら 0 を返します。
• そうでない場合は以下を実行します。
  • m := 空の辞書を作成し、各要素の出現回数を記録します。
  • num := 各要素の出現回数の階乗の積
  • den := 要素数 n の階乗(n!)
  • den ÷ num を返します(小数点以下6桁に丸める)。

n! を各要素の出現回数の階乗で割ることで、重複する要素を含む配列でも「異なる順列の総数」を正しく求められます。異なる順列の総数が D 通りであれば、1回のシャッフルの成功率は 1/D、期待シャッフル回数は D になるのです。

実装例

理解を深めるために、以下のPythonコードを見てみましょう。

from math import factorial

def solve(nums):
    if nums == sorted(nums):
        return 0
    else:
        m = {}
        for i in nums:
            if i in m:
                m[i] += 1
            else:
                m[i] = 1
        num = 1
        for i in m:
            num *= factorial(m[i])

        den = factorial(len(nums))
        return round((den / num), 6)

nums = [5, 2, 7]
print(solve(nums))

入力

[5,2,7]

出力

6.0

まとめ

このプログラムは、配列が既にソートされていれば 0 を返し、そうでなければ重複を考慮した順列の総数を計算することで、ソート完了までの期待シャッフル回数を効率的に求めています。ボゴソート本体の平均計算量は O(n × n!) と非常に非効率ですが、期待値の計算自体はこのようにシンプルな数式で表せるのが興味深いポイントです。