โปรแกรมหาค่าคาดหวังของความถี่สูงสุดของผลลัพธ์นิพจน์ใน Python

สมมติว่ามี M นิพจน์ต่างกัน คำตอบอยู่ในช่วง 1 ถึง N ให้ x = max(f(i)) สำหรับ i=1..N โดย f(i) คือความถี่ของคำตอบ i ต้องหาค่าคาดหวังของ x

ตัวอย่าง M=3, N=3 ผลลัพธ์ = 2.2 เพราะลำดับที่เป็นไปได้ 10 แบบ ความถี่สูงสุดมีการกระจาย: 1 ครั้ง 1 แบบ, 2 ครั้ง 6 แบบ, 3 ครั้ง 3 แบบ E(x) = 1/10 + 2*6/10 + 3*3/10 = 22/10 = 2.2

ขั้นตอนการแก้ปัญหา

• ใช้ Inclusion-Exclusion Principle คำนวณจำนวนลำดับที่ max frequency <= k
• nCr() คำนวณ combination ด้วย memoization
• สำหรับ k=2..M+1 คำนวณจำนวนลำดับที่ max freq <= k
• หาความแตกต่างระหว่างค่าติดกันได้จำนวนที่ max freq = k
• ค่าคาดหวัง = sum(k * P(max freq = k))

ตัวอย่างโค้ด

combination = {}

def nCr(n, k_in):
    k = min(k_in, n - k_in)
    if n < k or k < 0:
        return 0
    elif (n, k) in combination:
        return combination[(n, k)]
    elif k == 0 or n == k:
        return 1
    else:
        a = 1
        for cnt in range(k):
            a *= (n - cnt)
            a //= (cnt + 1)
            combination[(n, cnt + 1)] = a
        return a

def solve(M, N):
    arr = []
    for k in range(2, M + 2):
        a = 1
        s = 0
        for i in range(M // k + 2):
            if M < i * k:
                break
            s += a * nCr(N, i) * nCr(N - 1 + M - i * k, M - i * k)
            a *= -1
        arr.append(s)
    total = arr[-1]
    diff = [arr[0]] + [arr[cnt + 1] - arr[cnt] for cnt in range(M - 1)]
    output = sum(diff[cnt] * (cnt + 1) / total for cnt in range(M))
    return output

M = 3
N = 3
print(solve(M, N))

อินพุต

3, 3

เอาต์พุต

2.2