Chương trình Python tìm số phần tử tối thiểu để tạo chuỗi

Khi cần tìm số lượng phần tử tối thiểu từ list để tạo thành chuỗi mục tiêu (chứa tất cả ký tự của chuỗi mục tiêu), ta dùng set, combinations, issubset.

Ví dụ

from itertools import combinations

my_list = ["python", "is", "fun", "to", "learn"]
print("Danh sách là:")
print(my_list)

my_target_str = "onis"
my_result = -1
my_set_string = set(my_target_str)
complete_val = False

for value in range(0, len(my_list) + 1):
    for sub in combinations(my_list, value):
        temp_set = set(ele for subl in sub for ele in subl)
        if my_set_string.issubset(temp_set):
            my_result = value
            complete_val = True
            break
    if complete_val:
        break

print("Kết quả là:")
print(my_result)

Kết quả đầu ra

Danh sách là:
['python', 'is', 'fun', 'to', 'learn']
Kết quả là:
2

Giải thích

• Chuỗi mục tiêu "onis" → set {'o','n','i','s'}.
• Thử tổ hợp 1 phần tử: không tập nào chứa đủ 4 ký tự.
• Thử tổ hợp 2 phần tử: ("python", "is") → union set chứa o,n,i,s → đủ → kết quả = 2.
• Dùng combinations sinh tổ hợp, issubset kiểm tra bao hàm.

Lưu ý: Thuật toán brute-force, phù hợp list nhỏ. Với list lớn, cần thuật toán tối ưu (set cover problem).