Thuật toán có thể tìm tất cả các tập phân tách từ tập hợp các bộ là gì?

Question

Tôi có bộ 'n' (n < 10). Mỗi bộ có thể cho phép nói, 1000 yếu tố. Tôi muốn tìm tất cả các bộ phân chia cho các bộ này. Ví dụ: tôi có các bộ

A = {2,5,6,7}, B = {5,1} and C = {5,7}. 

Sau đó, đầu ra sẽ là {{5}, {2,6}, {1}, {7}}. Thuật toán này có thể là gì? Tôi nghĩ về việc tìm các bộ phân tách cặp đôi và sau đó sử dụng các bộ mới (phân tách) này để tìm lại các bộ phân tách khỏi các tập hợp còn lại. Nhưng điều này sẽ không quy mô tốt. Hy vọng điều này sẽ giúp: Diagram Example

Answer 1

Bạn có thể xem xét vấn đề của mình dưới dạng bản đồ hai boolean, các phần tử là các hàng, bộ là cột và boolean là câu trả lời của câu hỏi là phần tử được bao gồm trong bộ này. Ví dụ: ví dụ của bạn sẽ là:

t A B C 
2 1 0 0 
5 1 1 1 
6 1 0 0 
7 1 0 1 
1 0 1 0 

Sau đó tạo khóa cho mỗi phần tử mô tả các điểm khác biệt đặt trong và đăng ký phần tử này trên bản đồ.

Ví dụ nếu chúng ta xem xét các chức năng then chốt tạo ra như một cái gì đó như thế này:

int keyFunction(bool Xa, bool Xb, bool Xc) { 
    int key =0; 
    if (Xa) {key+=4;} 
    if (Xb) {key+=2;} 
    if (Xc) {key+=1;} 
    return key; 
} 

Sau đó chúng tôi có thể tạo ra bản đồ:

Key ElementsQueue 
0 [] 
1 [] 
2 [1] 
3 [] 
4 [2,6] 
5 [7] 
6 [] 
7 [5] 

và gửi lại các yếu tố của bản đồ này.