โปรแกรมค้นหาผลรวมของอาร์เรย์ย่อยที่คาดหวังของอาร์เรย์ที่กำหนดโดยดำเนินการบางอย่างใน Python

โปรแกรมค้นหาผลรวมของอาร์เรย์ย่อยที่คาดหวังของอาร์เรย์ที่กำหนดโดยดำเนินการบางอย่าง

สมมติว่าเรามีอาร์เรย์ A ที่มีขนาดเป็น n และมีค่าสองค่า p และ q เราสามารถดำเนินการเหล่านี้ได้ใน A.

• สุ่มเลือกสองดัชนี (l, r) โดยที่ l
• สุ่มเลือกสองดัชนี (l, r) โดยที่ l

หลังจากดำเนินการครั้งแรก p จำนวนครั้งและการดำเนินการครั้งที่สอง q ครั้ง เราจะสุ่มเลือกดัชนีสองตัว l &r โดยที่ l

ดังนั้น หากอินพุตเป็น A =[1,2,3] p =1 q =1 ผลลัพธ์จะเป็น 4.667 เพราะ

ขั้นตอนที่ 1:เรามีสามทางเลือก –

• swap(0, 1) ดังนั้นอาร์เรย์จะเป็น 2 1 3

• swap(0, 2) ดังนั้นอาร์เรย์จะเป็น 3 2 1

• swap(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
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
    • toret[i] :=toret[i] + a[i, j]*v[j]
• คืนโทเร็ต
• จากวิธีหลัก ให้ทำดังนี้:
• n :=ขนาดของ A
• temp :=รายการใหม่
• swp :=(n - 3) /(n - 1)
• swapvalp :=((swp^p)*(n - 1) + 1) /n
• swapvalm :=(1 - (swp^p)) /n
• rev :=รายการใหม่ที่ว่างเปล่า
• dotv :=รายการว่างใหม่
• สำหรับฉันในช่วง 0 ถึง n - 1 ทำ
  • swaprow :=รายการใหม่ที่ว่างเปล่า
  • revrow :=รายการใหม่ที่ว่างเปล่า
  • สำหรับ j ในช่วง 0 ถึง n - 1 ทำ
    • ใส่ swapvalm ที่ส่วนท้ายของ swaprow
    • แทรก 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))
  • ใส่สวอปโรว์ที่ส่วนท้ายของอุณหภูมิ
  • ใส่ revrow ที่ส่วนท้ายของ rev
  • แทรก 2*((i+1)*(n-i) - 1)/(n*(n-1)) ที่ส่วนท้ายของ dotv
• A :=matmul(ชั่วคราว, A, n)
• สำหรับฉันในช่วง 0 ถึง q ทำ
  • A :=matmul(rev, A, n)
• tot :=0.0
• สำหรับ i ในช่วง 0 ถึง n ให้ทำ
  • tot :=tot + dotv[i]*A[i]
• คืนทีโอที

ตัวอย่าง

ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -

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