डुप्लिकेट के बिना tuples को पूरा किया जा सकता है कि सबसेट ढूँढना

Question

हमारे पास सेट A_1, .., A_n का संग्रह है। लक्ष्य प्रत्येक पुराने सेट के लिए नए सेट ढूंढना है।

newA_i = {a_i in A_i such that there exist (a_1,..,a_n) in (A1,..,An) with no a_k = a_j for all k and j} 

तो शब्दों में यह है कि हम उस सेट से एक टपल (a_1, .. a_n) (A_1, .., a_n) ऐसी है कि बनाने के लिए इस्तेमाल नहीं किया जा सकता a_i से सभी तत्वों को दूर का कहना है टुपल में डुप्लीकेट नहीं होते हैं।

मेरा प्रश्न यह है कि इन नए सेटों की त्वरित गणना कैसे करें। यदि आप सभी संभावित वी उत्पन्न करके इस परिभाषा को लागू करते हैं तो यह घातीय समय लेगा। क्या आप एक बेहतर एल्गोरिदम जानते हैं?

संपादित करें: यहां एक उदाहरण है।

A_1 = {1,2,3,4} 
A_2 = {2}. 

लो अब नए सेट इस तरह दिखेगा:

newA_1 = {1,3,4} 
newA_2 = {2} 

2 A_1 से हटा दिया गया है अगर आप इसे चुनें टपल हमेशा होगा, क्योंकि (2,2) जो क्योंकि यह अमान्य है डुप्लीकेट शामिल है। दूसरी तरफ 1,3,4 मान्य हैं क्योंकि (1,2), (3,2) और (4,2) मान्य टुपल्स हैं।

एक और उदाहरण:

A_1 = {1,2,3} 
A_2 = {1,4,5} 
A_3 = {2,4,5} 
A_4 = {1,2,3} 
A_5 = {1,2,3} 

अब नए सेट कर रहे हैं:

newA_1 = {1,2,3} 
newA_2 = {4,5} 
newA_3 = {4,5} 
newA_4 = {1,2,3} 
newA_5 = {1,2,3} 

1 और 2 सेट 2 और 3 से निकाल दिए जाते हैं क्योंकि यदि आप चाहें तो 1 या 2 इन सेटों से आप सेट 1, 4 और 5 के लिए केवल 2 मान शेष होंगे, इसलिए आपके पास हमेशा (_,1,_,_,_) या (_,_,2,_,_) जैसा दिखने वाले टुपल्स में डुप्लिकेट होंगे।

यह समस्या मुश्किल लगती है, लेकिन यदि बहुपद समय एल्गोरिदम था तो यह बहुत अच्छा होगा।

यह देखने का एक और तरीका है सेट पर A_i सेट करें और दाईं ओर के मान, एक सेट को जोड़ने वाली रेखा के साथ और मान सेट में होने पर मान के साथ।

Answer 1

मुझे लगता है कि असाइनमेंट एल्गोरिदम यहां मदद कर सकता है। बुनियादी कदम एआई में से किसी एक नंबर पर ठीक करना होगा और फिर देखें कि क्या उस नंबर का उपयोग अज से चुने गए अन्य लोगों के साथ किया जा सकता है ताकि प्रत्येक सेट से दोहराए बिना किसी संख्या का चयन किया जा सके। लोगों के रूप में संख्याओं के बारे में सोचें, और सेट एजे में संख्या उन लोगों के रूप में करें जिन्हें कार्य करने के लिए इस्तेमाल किया जा सकता है। फिर प्रत्येक अज से एक अलग प्रतिनिधि खोजने की समस्या प्रत्येक कार्य को एक अलग व्यक्ति को सौंपने की समस्या है।

विकिपीडिया असाइनमेंट समस्या का व्यवहार करता है क्योंकि सभी असाइनमेंट संभव हैं और प्रत्येक http://en.wikipedia.org/wiki/Assignment_problem के लिए लागत है। हमारे मामले में हम 0 और 1 का उपयोग लागत के रूप में कर सकते हैं और कर सकते हैं और यह नहीं देख सकते कि शून्य लागत का जवाब है या नहीं।

Answer 2

मैं अभी भी इसे हल करने के बारे में सोच रहा हूं, लेकिन मैंने यह प्रश्न फिर से लिखने का फैसला किया कि यह मुझे कोई प्रेरणा देता है या नहीं।

देखते हुए एन का एक सेट सेट:

A_i = {a_i0, a_i1, ..., a_ij, ...} 

लगता है

B_i such that x is in B_i if and only if: 
    x is in A_i and 
    there exists {c_0, c_1, c_2, c_3, ..., c_N} such that 
     c_i = x and 
     c_k is in A_k for all k and 
     c_k != c_l for all k != l