Python程式：透過一些操作找到給定陣列子陣列的期望和

程式：透過一些操作找到給定陣列子陣列的期望和

假設我們有一個大小為n的陣列A和兩個值p和q。我們可以對A執行以下操作。

  • 隨機選擇兩個索引(l, r)，其中l < r，然後交換A[l]和A[r]
  • 隨機選擇兩個索引(l, r)，其中l < r，然後反轉A從索引l到r的子陣列。

在執行p次第一個操作和q次第二個操作之後，我們隨機選擇兩個索引l和r，其中l < r，並計算S = A[l..r]的所有元素的和，然後我們必須找到S的期望值。

因此，如果輸入類似於A = [1,2,3] p = 1 q = 1，則輸出將為4.667，因為

步驟1：我們有三個選擇：

  • 交換(0, 1)，所以陣列將變為2 1 3

  • 交換(0, 2)，所以陣列將變為3 2 1

  • 交換(1, 2)，所以陣列將變為1 3 2

步驟2：對於每個結果，我們再次有三個選擇：

  • [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。所以這9個數組中的每一個都將具有3個具有相同機率的可能和。例如，對於[1 2 3]，我們可以得到1+2、2+3和1+2+3。對於此輸入，總共有27個結果，可以透過找到所有27個S的和並將其除以27來計算期望值。

為了解決這個問題，我們將遵循以下步驟：

  • 定義一個函式matmul()。這將接收a, v, n
  • toret := 一個大小為n的陣列，並用0填充
  • 對於i in range 0 到 n - 1，執行
    • 對於j in range 0 到 n - 1，執行
      • toret[i] := toret[i] + a[i, j]*v[j]
  • 返回toret
  • 從主方法中，執行以下操作
  • n := A的大小
  • temp := 一個新的列表
  • swp := (n - 3) /(n - 1)
  • swapvalp := ((swp^p)*(n - 1) + 1) /n
  • swapvalm :=(1 - (swp^p)) /n
  • rev := 一個新的空列表
  • dotv := 一個新的空列表
  • 對於i in range 0 到 n - 1，執行
    • swaprow := 一個新的空列表
    • revrow := 一個新的空列表
    • 對於j in range 0 到 n - 1，執行
      • 在swaprow的末尾插入swapvalm
      • 在revrow的末尾插入2*(min(i, j, (n-i-1) 和 (n-j-1+1))/(n*(n - 1))
    • swaprow := 一個新的空列表
    • revrow := 一個新的空列表
    • 對於j in range 0 到 n - 1，執行
    • swaprow[i] := swapvalp
    • revrow[i] := 1.0 - 2*((i + 1)*(n - i) - min((i+1) 和 (n - i)))/(n*(n-1))
    • 在temp的末尾插入swaprow
    • 在rev的末尾插入revrow
    • 在dotv的末尾插入2*((i+1)*(n-i) - 1)/(n*(n-1))
  • A := matmul(temp, A, n)
  • 對於i in range 0 到 q，執行
    • A := matmul(rev, A, n)
  • tot := 0.0
  • 對於i in range 0 到 n，執行
    • tot := tot + dotv[i]*A[i]
  • 返回tot

示例

讓我們看看下面的實現以更好地理解：

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

更新於：2021年10月11日

287 次瀏覽

開啟你的職業生涯

完成課程獲得認證

開始
廣告