通过在Python中执行一些操作查找给定数组的子数组的期望和的程序

通过执行一些操作查找给定数组的子数组的期望和的程序

假设我们有一个大小为n和两个值p和q的数组A。我们可以在A上执行以下操作。

随机选择两个索引(l，r)，其中l
随机选择两个索引（l，r），其中l

在执行第一次操作p次和第二次操作q次后，我们随机选择两个索引l和r，其中l

因此，如果输入是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个结果，可以通过找到所有27S的总和并将其除以27来计算期望值。

要解决此问题，我们将执行以下步骤 –

定义函数matmul()。这将采取a，v，n
toret：一个大小为n的数组，填充为0
对于i从0到n-1，做
- 对于j从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从0到n-1，做
- swaprow：一行新的空列表
- revrow：一行新的空列表
- 对于j从0到n-1，做
  - 在swaprow末尾插入swapvalm
  - 在revrow末尾插入2 *（i，j，（n-i-1）和（n-j-1 + 1）的最小值）/（n *（n-1））
- swaprow：一行新的空列表
- revrow：一行新的空列表
- 对于j从0到n-1，做
- swaprow [i]：= swapvalp
- revrow [i]：= 1.0-2 （（i + 1）（n-i）-（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从0到q，做
- A：= matmul（rev，A，n）
tot：= 0.0
对于i从0到n，做
- tot：= tot + dotv [i] * A [i]
返回tot

示例

让我们看一下以下实现，以便更好地了解 –

def matmul(a, v, n):
   # 初始化长度为n的全0数组
   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)))

   # 先乘置换矩阵再乘反转矩阵q次
   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))