एल्गोरिथ्म आम सबसेट

Question

मेरे पास है खोजने के लिए एन सेट एस _मैं नंबर की, एक अलग आकार के प्रत्येक की संख्या। चलो मीटर, मीटर ... मीटर _n संबंधित सेट के आकार होना (मीटर _मैं = | एस _मैं |), और एम सबसे बड़ा सेट का आकार बनें। मुझे सामान्य सबसेट मिलना है जिनमें कम से कम दो संख्याएं हों। उदाहरण:

Set Items 
1 10,80,22 
2 72, 10, 80, 26,50 
3 80, 
4 10, 22 
5 22, 72, 10, 80, 26,50 

तो नतीजा यह है कि

Items    Found in sets 
10, 22    1, 4 
10, 80    1, 2, 5 
10, 80, 22   1, 5 
10, 72, 80, 26, 50 2, 5 

तरह होगा तो कैसे इस समस्या को स्वचालित करने के लिए और संबंधित समाधान के लिए उम्मीद जटिलता क्या है? मुझे इसे यथासंभव तेज़ होने की आवश्यकता है।

Answer 1

मेरे पास कुछ सुझाव हैं। जब आप उस सेट में किसी संख्या की गणना करने के लिए लूप में लूप करते हैं, तो आपको सेट में सभी आइटम सॉर्ट करना चाहिए। चेक के लिए आपको शर्त जोड़नी चाहिए, यह संख्या आपके खोज मूल्य से अधिक है और ब्रेक का उपयोग करें; लूप के अंत के लिए।

Answer 2

आप ऐसा कर सकता है -

1. एक हैश तालिका & डालने बनाएं कुंजी अपने मद से प्रत्येक सेट के रूप में & मूल्यों वे संबंध रखते हैं के रूप में। Eg: 10:[0,1,3,4] 80:[0,1,2,4] 22:[0,3,4] 72:[1,4] 26:[1,4] 50:[1,4]

2. इसके बाद हैश तालिका में प्रत्येक 2 तत्वों के लिए, कुंजी के मानों का चौराहे पाएं। यहां (10, 80) का चौराहे [0,3,4] देता है। ऐसा करने के लिए (10,22) (10,72) ... आपका परिणाम है। (एम^2) हे [यह कर सकते थे -

3. जटिलता - हैश तालिका में एम आइटम सम्मिलित करने के लिए - हे (एम) हैश तालिका में प्रत्येक कुंजी खोज - हे (1) चौराहे के प्रमुख के मूल्य के ऑपरेशन अनुकूलित किया जा सकता है]

पूरी तरह से मैं कहूंगा कि यह ओ (एम^2) algo है। लेकिन अगर "आइटम" का आकार प्रत्येक "सेट" में बड़ा नहीं है, तो आपको अधिक प्रदर्शन हिट दिखाई नहीं देगी।

Answer 3

एक समाधान मैं के बारे में सोच सकते हैं:

एक हैश तालिका का उपयोग करें, कि "पंक्ति" है, जो ओ (एम * एम) समय है में की संख्या के "संख्या की एक जोड़ी" सभी संयोजन उत्पन्न करते हैं।

फिर उन हैंश कुंजी के रूप में उपयोग करें, मुख्य सरणी अनुक्रमणिका में मैपिंग।

For each row of those N elements, 
    do the step above... and if the hash already maps to a number, then it is a match, 
    then return the pair, or else just put those in the hash 

यह है हे (एन * एम * एम)

अद्यतन: के रूप में आप टिप्पणी में कहते हैं, कि एम अधिकतम 15 हो सकता है, तो हे (एन * एम * एम) वास्तव में ओ (एन) के समान ही है।

---

अपने प्रारंभिक सवाल सभी जोड़ों को मिल रहा है, तो

For each row of those N elements, 
    do the step first mentioned... and if the hash already maps to a number, 
    then it is a match and just print out the pair if this pair is not printed yet 
    and in any event, put the mapping into the hash 

to tell whether a pair has been printed, created another hash, such as 
    printed_or_not[i,j] = true or false, 
    and make sure to check printed_or_not[i,j] or printed_or_not[j, i] 
    because not need to print again if just different order 

Answer 4

आप अपने सभी सेट जोड़ो में चौराहे करते हैं और उसके बाद सभी परिणाम है कि आकार> = 2 हैं इकट्ठा करने के लिए कहा जा रहा है

ओ (एन^2) जोड़े हैं। चौराहे करना प्रत्येक के लिए ओ (एम) है। सभी परिणामों को इकट्ठा करें, डुप्लिकेट को काम करने के लिए सेट सामग्री द्वारा क्रमबद्ध करें एन^2 लॉग एन^2 (सबसे खराब मामला यह है कि प्रत्येक जोड़ी के लिए चौराहे अलग है इसलिए ओ (एन^2) परिणाम सेट हो सकता है)

तो मुझे लगता है कि जटिलता ओ ((एन^2 + एन लॉग एन) * एम)

लेकिन कहीं भी एक त्रुटि संभव है।

पॉल

Answer 5

मूल प्रश्न के रूप में तेजी से संभव के रूप में एक चर्चा बनाने के लिए पूछता है के बाद से, यह इस प्रकार कम किया जा सकता है है।

सबसे पहले, चर्चा करें कि आउटपुट आपके इनपुट के लिए घातीय है या नहीं। मान लें कि आपके पास 2 तत्व हैं, और एन सेट हैं। मान लें कि प्रत्येक तत्व प्रत्येक सेट से संबंधित है; इसके लिए आपके इनपुट के रूप में एन लाइनों की आवश्यकता होगी। फिर, आप कितनी लाइनों को मुद्रित करना चाहिए? (2 ^एन) समय मुद्रण

1,2  1,2 
1,2  1,3 
..... 
1,2  1,N 
1,2  2,1 
..... 
1,2  1,2,3 
..... 
1,2  1,2,3,...N 

आप हे खर्च करने के लिए जा रहे हैं के बाद से,:

मुझे लगता है कि आप, 2 ^एन एन -1 लाइनों मुद्रित करने के लिए इस तरह के लिए जा रहे हैं आप इस जानकारी की गणना करने के लिए इस पृष्ठ पर किसी भी सुझाव को चुन सकते हैं-आप किसी भी एक्सपोनेंट द्वारा पकड़े गए हैं।

यह तर्क आपकी चर्चा को बहुत तेज बना देगा।