通过在 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=1q=1，那么输出将是4.667，因为
第1步：我们有三个选择-
swap(0,1)所以数组将是213
swap(0,2)所以数组将是321
swap(1,2)所以数组将是132
第2步：对于每个结果，我们再次有三个选择-
[213]到[123],[312],[231]
[321]到[231],[123],[312]
[132]到[312],[231],[123]
有9个可能的数组，所以概率是1/9。所以这9个数组中的每一个都有3个可能的和，概率相等。例如，[123]，我们可以得到1+2、2+3和1+2+3。此输入共有27个结果，可以通过求所有27S的总和除以27来计算期望值。
示例
让我们看看以下实现以获得更好的理解-
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