แนวคิด
โจทย์แบบ Set Cover: หาจำนวนคำน้อยที่สุดจากลิสต์ ที่รวมตัวอักษร (unique characters) ครอบคลุมสตริงเป้าหมายทั้งหมด ใช้ itertools.combinations ลองทุกชุดย่อย
ตัวอย่างโค้ด
from itertools import combinations
my_list = ["python", "is", "fun", "to", "learn"]
print("ลิสต์คำ:", my_list)
my_target_str = "onis"
print("สตริงเป้าหมาย:", my_target_str)
target_set = set(my_target_str)
my_result = -1
found = False
for r in range(len(my_list) + 1):
for combo in combinations(my_list, r):
# รวมตัวอักษรใน combo
combined = set(''.join(combo))
if target_set.issubset(combined):
my_result = r
found = True
break
if found:
break
print("จำนวนคำขั้นต่ำ:", my_result)
ผลลัพธ์
ลิสต์คำ: ['python', 'is', 'fun', 'to', 'learn']
สตริงเป้าหมาย: onis
จำนวนคำขั้นต่ำ: 2
คำอธิบาย
- target_set = {'o', 'n', 'i', 's'}
- ลองชุด 1 คำ: ไม่มีคำไหนครอบคลุมทั้ง 4 ตัวอักษร
- ลองชุด 2 คำ: "python" + "is" -> {'p','y','t','h','o','n','i','s'} ครอบคลุม -> ได้ 2
หมายเหตุประสิทธิภาพ
อัลกอริทึมนี้เป็น O(2ⁿ) ใช้ได้กับลิสต์เล็ก (n ≤ 20) สำหรับข้อมูลใหญ่ ใช้ Greedy Approximation หรือ Integer Programming
