सेट के सेट से सभी डिस्जिइंट सेट खोजने के लिए एल्गोरिदम क्या हो सकता है?

Question

मेरे पास 'एन' सेट हैं (एन < 10)। प्रत्येक सेट कह सकता है, 1000 तत्व। मैं इन सेटों के लिए सभी अपमान सेट ढूंढना चाहता हूं। कहते हैं, उदाहरण के लिए, मेरे पास सेट

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

फिर उत्पादन {{5}, {2,6}, {1}, {7}} होगा। इसके लिए एल्गोरिदम क्या हो सकता है? मैंने pairwise disjoint सेट खोजने के बारे में सोचा और फिर इन नए (डिसजॉइंट) सेट का उपयोग करके सेट किए गए सेट से अलग सेट ढूंढने के लिए। लेकिन यह अच्छी तरह से पैमाने पर नहीं होगा। उम्मीद है कि यह मदद करता है: Diagram Example

Answer 1

आप अपनी समस्या को बूलियन दो प्रविष्टि मानचित्र के रूप में देख सकते हैं, पंक्तियां तत्व हैं, कॉलम होने के सेट हैं और बुलियन प्रश्न का उत्तर है जो सेट में शामिल तत्व है। उदाहरण के लिए अपने उदाहरण होगा:

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

फिर सेट प्रत्येक तत्व विभिन्न वर्णन करने के लिए एक महत्वपूर्ण यह है बना सकते हैं और किसी नक्शे में इस तत्व रजिस्टर।

उदाहरण के लिए अगर हम कुछ इस तरह के रूप में प्रमुख निर्माण समारोह पर विचार करें:

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; 
} 

हम तो नक्शा बना सकते हैं:

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

और इस नक्शे के तत्वों लौटने।