Trong quá trình xử lý dữ liệu, đôi khi chúng ta không chỉ cần tìm giao điểm của hai tập hợp mà còn cần xác định xem một phần tử bất kỳ xuất hiện trong những tập hợp nào trong một nhóm gồm nhiều tập hợp khác nhau. Bài viết này hướng dẫn cách xây dựng một bản đồ (mapping) để quản lý mối quan hệ giữa các phần tử và các tập hợp chứa chúng một cách hiệu quả.

Mục tiêu bài toán

Giả sử chúng ta có 4 tập hợp sau:

• C1 = {11, 22, 13, 14}
• C2 = {11, 32, 23, 14, 35}
• C3 = {11, 22, 38}
• C4 = {11, 22, 33, 14, 55, 66}

Kết quả mong muốn là xác định được nguồn gốc của từng phần tử, ví dụ: phần tử 11 thuộc cả 4 tập hợp, phần tử 22 thuộc C1, C3, C4, và phần tử 14 thuộc C1, C2, C4.

Quy trình thực hiện

Để tối ưu hóa hiệu suất, chúng ta có thể thực hiện theo các bước sau:

1. Sắp xếp hoặc duyệt qua các tập hợp theo kích thước (từ nhỏ nhất đến lớn nhất) để giảm thiểu số lượng phép so sánh ban đầu.
2. Sử dụng một cấu trúc dữ liệu từ điển (dictionary) để lưu trữ khóa là giá trị của phần tử và giá trị là danh sách các chỉ mục (index) của tập hợp chứa nó.
3. Duyệt qua từng phần tử trong mỗi tập hợp và cập nhật vào từ điển kết quả.

Mã nguồn triển khai

Dưới đây là đoạn mã Python sử dụng thư viện tiêu chuẩn để giải quyết bài toán này một cách tối ưu:

def find_element_memberships(sets_list):
    """
    Xác định các tập hợp chứa từng phần tử duy nhất.
    """
    # Bản đồ lưu trữ: {phần_tử: [danh_sách_chỉ_mục_tập_hợp]}
    membership_map = {}

    # Duyệt qua từng tập hợp cùng với chỉ mục của nó
    for idx, current_set in enumerate(sets_list):
        for element in current_set:
            if element not in membership_map:
                membership_map[element] = []
            
            # Thêm chỉ mục của tập hợp vào danh sách nếu chưa tồn tại
            if idx not in membership_map[element]:
                membership_map[element].append(idx)
    
    return membership_map

if __name__ == "__main__":
    # Dữ liệu mẫu ban đầu
    sets_collection = [
        {11, 22, 13, 14},           # C0
        {11, 32, 23, 14, 35},       # C1
        {11, 22, 38},               # C2
        {11, 22, 33, 14, 55, 66}    # C3
    ]

    print("--- Kết quả phân tích thành viên ---")
    results = find_element_memberships(sets_collection)
    
    # Sắp xếp kết quả theo giá trị phần tử để dễ quan sát
    for val in sorted(results.keys()):
        print(f"Phần tử {val}: Xuất hiện ở các tập hợp chỉ mục {results[val]}")

Kết quả đầu ra

Khi chạy đoạn mã trên với bộ dữ liệu mẫu, chúng ta sẽ nhận được kết quả liệt kê chi tiết:

--- Kết quả phân tích thành viên ---
Phần tử 11: Xuất hiện ở các tập hợp chỉ mục [0, 1, 2, 3]
Phần tử 13: Xuất hiện ở các tập hợp chỉ mục [0]
Phần tử 14: Xuất hiện ở các tập hợp chỉ mục [0, 1, 3]
Phần tử 22: Xuất hiện ở các tập hợp chỉ mục [0, 2, 3]
Phần tử 23: Xuất hiện ở các tập hợp chỉ mục [1]
Phần tử 32: Xuất hiện ở các tập hợp chỉ mục [1]
Phần tử 33: Xuất hiện ở các tập hợp chỉ mục [3]
Phần tử 35: Xuất hiện ở các tập hợp chỉ mục [1]
Phần tử 38: Xuất hiện ở các tập hợp chỉ mục [2]
Phần tử 55: Xuất hiện ở các tập hợp chỉ mục [3]
Phần tử 66: Xuất hiện ở các tập hợp chỉ mục [3]

Phân tích hiệu năng

Phương pháp này sử dụng bảng băm (hash map) của Python giúp việc tra cứu và chèn dữ liệu đạt độ phức tạp trung bình là O(1). Tổng độ phức tạp của thuật toán là O(N), trong đó N là tổng số lượng phần tử của tất cả các tập hợp cộng lại. Đây là cách tiếp cận hiệu quả hơn nhiều so với việc thực hiện các phép giao tập hợp lặp đi lặp lại giữa từng cặp tập hợp.