कुछ संचालन करके किसी दिए गए सरणी के उप-सरणियों का अपेक्षित योग खोजने का कार्यक्रम
मान लीजिए हमारे पास एक सरणी A है जिसका आकार n है और दो मान p और q हैं। हम ये ऑपरेशन A.
. पर कर सकते हैं- यादृच्छिक रूप से दो अनुक्रमणिका (l, r) का चयन करें जहां l
- यादृच्छिक रूप से दो अनुक्रमणिका (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 से विभाजित करके अपेक्षित मान की गणना की जा सकती है।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
आइए बेहतर समझ पाने के लिए निम्नलिखित कार्यान्वयन देखें -
उदाहरण
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
