โปรแกรมคำนวณค่าเฉลี่ยของค่าพิเศษทั้งหมดสำหรับทุกการเรียงสับของรายการใน Python

สมมติว่าเรามีรายการขององค์ประกอบ เราสามารถคำนวณค่า S โดยอัลกอริทึมต่อไปนี้:

while size of L > 1 is non-zero, do
    a := L[0]
    b := L[1]
    remove L[1]
    L[0] := a + b + a*b
return L[0] mod (10^9 + 7)

ในที่นี้ เราต้องหาค่าเฉลี่ยของค่า S ทั้งหมดที่คำนวณจากทุกการจัดเรียงที่เป็นไปได้ของ L

เช่น ถ้าอินพุตคือ L = [5,3,4] ผลลัพธ์จะเป็น 119 เพราะสำหรับทุกการเรียงสับของ L ค่า S คือ 119 ดังนั้นค่าเฉลี่ยก็คือ 119 เช่นกัน

วิธีแก้ปัญหา

ทำตามขั้นตอนต่อไปนี้:

• m := 10^9+7
• li := รายการของ x+1 สำหรับทุก x ใน L
• prod := 1
• สำหรับแต่ละ i ใน li:
  • prod := prod * i
  • prod := prod mod m
• return (prod-1) mod m

ตัวอย่าง

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

def solve(L):
    m = 10**9+7
    li = [x+1 for x in L]
    prod = 1
    for i in li:
        prod *= i
        prod %= m
    return (prod-1) % m

L = [5,3,4]
print(solve(L))

อินพุต

[5,3,4]

เอาต์พุต

119