หาคู่ตัวเลขจากอาร์เรย์ที่ให้ค่า nCr สูงสุดใน Python

หาคู่ (n, r) ที่ทำให้ nCr มากที่สุด

กำหนดอาร์เรย์ arr ขนาด n ต้องการหาคู่ arr[i] และ arr[j] ที่ทำให้ arr[i] C arr[j] (จำนวนวิธีเลือก) มีค่ามากที่สุด หากมีหลายคู่ ให้คืนคู่ใดคู่หนึ่ง

ตัวอย่าง: [4, 1, 2] → คู่ (4, 2) เนื่องจาก 4C2 = 6 สูงสุด

สังเกตสำคัญ

สำหรับ n คงที่ ค่า nCr จะมากที่สุดเมื่อ r ใกล้ n/2 ดังนั้นกลยุทธ์คือ:

1. เรียงอาร์เรย์จากน้อยไปมาก
2. เลือก N = arr[-1] (ค่ามากสุด) เป็น n
3. หา r ในอาร์เรย์ที่ใกล้ N/2 มากที่สุด

อัลกอริทึม

• ถ้า N เป็นคี่: first = N//2, second = first+1 หาในอาร์เรย์ค่าที่ใกล้ first (ทางซ้าย) และ second (ทางขวา) มากที่สุด เลือกด้านที่ใกล้กว่า
• ถ้า N เป็นคู่: max = N//2 หาค่าในอาร์เรย์ (ยกเว้นตัวสุดท้าย) ที่มีความต่างจาก max น้อยที่สุด

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

def findMatrixPair(v, n):
    v.sort()
    N = v[n - 1]
    if N % 2 == 1:
        first = N // 2
        second = first + 1
        res1 = res2 = 3 * (10 ** 18)
        left = right = -1
        temp = -1
        for i in range(n):
            if v[i] > first:
                temp = i
                break
            else:
                diff = first - v[i]
                if diff < res1:
                    res1 = diff
                    left = v[i]
        right = v[temp]
        diff1 = first - left
        diff2 = right - second
        if diff1 < diff2:
            print(N, left)
        else:
            print(N, right)
    else:
        mx = N // 2
        res = 3 * (10 ** 18)
        R = -1
        for i in range(n - 1):
            diff = abs(v[i] - mx)
            if diff < res:
                res = diff
                R = v[i]
        print(N, R)

v = [4, 1, 2]
findMatrixPair(v, len(v))  # Output: 4 2