Python: หาคู่/กลุ่ม K ตัวที่มีผลรวมเท่ากับ N (Cartesian Product)

บทนำ

โจทย์: จากลิสต์ตัวเลข หาคอมบิเนชัน K ตัว (ซ้ำได้) ที่มีผลรวมเท่ากับ N ใช้ itertools.product สร้าง Cartesian product แล้วกรองด้วย sum()

หลักการ

• product(my_list, repeat=K): สร้างทุกค่าที่เป็นไปได้ของ K ตัว (允許重複)
• ตรวจสอบ sum(combo) == N
• เก็บผลลัพธ์ที่ผ่านเกณฑ์

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

from itertools import product

my_list = [45, 32, 67, 11, 88, 90, 87, 33, 45, 32]
N = 77  # ผลรวมเป้าหมาย
K = 2   # จำนวนตัวในแต่ละกลุ่ม

print(f"ลิสต์: {my_list}")
print(f"K = {K}, N = {N}")

result = []
for combo in product(my_list, repeat=K):
    if sum(combo) == N:
        result.append(combo)

print(f"พบ {len(result)} คู่:")
for combo in result:
    print(f"  {combo} = {sum(combo)}")

ผลลัพธ์

ลิสต์: [45, 32, 67, 11, 88, 90, 87, 33, 45, 32]
K = 2, N = 77
พบ 8 คู่:
  (45, 32) = 77
  (45, 32) = 77
  (32, 45) = 77
  (32, 45) = 77
  (45, 32) = 77
  (45, 32) = 77
  (32, 45) = 77
  (32, 45) = 77

หมายเหตุ: ผลลัพธ์ซ้ำ

เนื่องจากลิสต์มีค่าซ้ำ (45 และ 32 ซ้ำ) และ product จัดเป็น ordered pairs (45,32) ต่างจาก (32,45) จึงได้ผลลัพธ์ซ้ำหลายชุด

เวอร์ชันปรับปรุง: ลบค่าซ้ำและไม่สนใจลำดับ

from itertools import combinations_with_replacement

# ใช้ combinations_with_replacement แทน product
# - ไม่อนุญาตให้สลับตำแหน่ง (45,32) = (32,45)
# - แต่ยังอนุญาตให้ซ้ำได้ (45,45) หากมี 45 ในลิสต์
unique_list = list(set(my_list))  # ลบค่าซ้ำในลิสต์ก่อน
result_unique = []
for combo in combinations_with_replacement(unique_list, K):
    if sum(combo) == N:
        result_unique.append(combo)

print(f"คู่ที่ไม่ซ้ำ (unique): {result_unique}")
# [(11, 66), (32, 45)]  ← สมมติมี 66 ในลิสต์

กรณี K > 2 (กลุ่ม 3 ตัวขึ้นไป)

def find_k_sum_groups(numbers, k, target):
    """หากลุ่ม k ตัวที่ sum = target (ไม่ซ้ำ, ไม่อยู่ในลำดับ)"""
    from itertools import combinations_with_replacement
    unique_nums = sorted(set(numbers))
    result = []
    for combo in combinations_with_replacement(unique_nums, k):
        if sum(combo) == target:
            result.append(combo)
    return result

# ทดสอบ K=3
print(find_k_sum_groups([1,2,3,4,5,6,7,8,9], 3, 15))
# [(1, 5, 9), (1, 6, 8), (2, 4, 9), (2, 5, 8), (2, 6, 7), (3, 4, 8), (3, 5, 7), (4, 5, 6)]

ประสิทธิภาพและข้อจำกัด

• product: O(n^K) - เร็วเฉพาะ K=2, nเล็ก
• combinations_with_replacement: O(C(n+K-1, K)) - น้อยกว่ามาก
• สำหรับ K ใหญ่หรือ N ใหญ่ ควรใช้ Dynamic Programming (Subset Sum / Knapsack)

สรุป

ใช้ itertools.product สำหรับ K=2 และอนุญาตลำดับ/ซ้ำ ใช้ combinations_with_replacement สำหรับ unique combinations ไม่อยู่ในลำดับ สำหรับปัญหาใหญ่ ควรเปลี่ยนอัลกอริทึม