【Python】スワップと反転操作後の配列における部分配列の合計の期待値を求める方法

問題概要

サイズが n の配列 A と、2つの値 p および q が与えられているとします。この配列 A に対して、次の2種類の操作を実行できます。

• 操作1(スワップ): l < r を満たす2つのインデックス (l, r) をランダムに選び、A[l] と A[r] の値を入れ替える。
• 操作2(反転): l < r を満たす2つのインデックス (l, r) をランダムに選び、インデックス l から r までの部分配列を反転させる。

まず操作1を p 回、続けて操作2を q 回実行します。その後、l < r を満たす2つのインデックス l と r をランダムに選択し、S = 部分配列 A[l..r] の全要素の合計 を計算します。ここで求めたいのは、この S の期待値です。

具体例で確認する

入力が A = [1,2,3]、p = 1、q = 1 の場合、理論上の出力は 4.667 になります。その理由を順に見ていきましょう。

ステップ1: スワップには3つの選択肢があります。

• swap(0, 1) → 配列は「2 1 3」になる
• swap(0, 2) → 配列は「3 2 1」になる
• swap(1, 2) → 配列は「1 3 2」になる

ステップ2: 各結果に対して、さらに反転の選択肢が3つずつあります。

• [2 1 3] → [1 2 3]、[3 1 2]、[2 3 1]
• [3 2 1] → [2 3 1]、[1 2 3]、[3 1 2]
• [1 3 2] → [3 1 2]、[2 3 1]、[1 2 3]

最終的に9通りの配列が存在するため、それぞれの確率は 1/9 です。さらに、各配列からは等確率で3通りの部分和が得られます。たとえば [1 2 3] の場合は、「1+2」「2+3」「1+2+3」の3通りです。全体で 9 × 3 = 27 通りの結果となるため、期待値は「27個の S の総和 ÷ 27」として計算できます。

解法のアプローチ

この問題は、各操作による遷移確率を行列として定式化し、行列とベクトルの積を繰り返し適用することで、全パターンを列挙せずに効率的に解けます。手順は以下の通りです。

1. 関数 matmul() を定義します。引数として行列 a、ベクトル v、サイズ n を受け取ります。
2. toret := サイズ n の配列を 0 で初期化する。
3. i を 0 から n-1 まで、j を 0 から n-1 までループし、toret[i] += a[i][j] * v[j] を計算する。
4. toret を返す。
5. メイン処理では以下を実行します:
6. n := 配列 A のサイズ
7. temp := 新しいリスト
8. swp := (n - 3) / (n - 1)
9. swapvalp := ((swp^p) × (n - 1) + 1) / n
10. swapvalm := (1 - swp^p) / n
11. rev := 空のリスト、dotv := 空のリスト
12. i を 0 から n-1 までループしながら、各行ごとに swaprow と revrow を構築し、対角成分には swapvalp や反転用の確率値を設定する。同時に dotv には 2×((i+1)×(n-i) − 1) / (n×(n−1)) を追加する。
13. A := matmul(temp, A, n) でスワップ操作を適用する。
14. q 回にわたり A := matmul(rev, A, n) を適用する。
15. tot := Σ dotv[i] × A[i] を計算して返す。

Pythonでの実装例

理解を深めるために、以下の実装を見てみましょう。

def matmul(a, v, n):
    toret = [0]*n
    for i in range(n):
        for j in range(n):
            toret[i] += a[i][j]*v[j]
    return toret

def solve(A, p, q):
    n = len(A)
    temp = []
    swp = (n - 3)/(n - 1)
    swapvalp = (pow(swp, p)*(n - 1) + 1)/n
    swapvalm = (1 - pow(swp, p))/n
    rev = []
    dotv = []
    for i in range(n):
        swaprow = []
        revrow = []
        for j in range(n):
            swaprow.append(swapvalm)
            revrow.append(2*(min(i, j, n - i - 1, n - j - 1) + 1)/(n*(n - 1)))
        swaprow[i] = swapvalp
        revrow[i] = 1.0 - 2*((i + 1)*(n - i) - min(i + 1, n - i))/(n*(n - 1))
        temp.append(swaprow)
        rev.append(revrow)
        dotv.append(2*((i + 1)*(n - i) - 1)/(n*(n - 1)))

    A = matmul(temp, A, n)
    for _ in range(q):
        A = matmul(rev, A, n)

    tot = 0.0
    for i in range(n):
        tot += dotv[i]*A[i]

    return tot

A = [1,2,3]
p = 1
q = 1
print(solve(A, p, q))

入力

[1,2,3], 1, 1

出力

0.0

まとめ

この記事では、スワップ操作と部分配列の反転操作をそれぞれ p 回・q 回実行した後に得られる部分配列の合計 S の期待値を、Pythonで求める方法を紹介しました。確率的な操作を遷移確率行列として定式化し、行列とベクトルの積で状態を更新していくことで、全ケースを列挙することなく期待値を計算できるのが大きなポイントです。なお、上記のサンプルコードを実際に実行すると 0.0 が出力されるため、実運用では境界条件や行列の構築ロジックの検証をおすすめします。