एल्गोरिथ्म जल्दी से लिंक किए हुए एकाधिक सूचियों

Question

मैं एक स्थिति है पर एक आंशिक आदेश प्राप्त करने, इस प्रकार के लिए:

• मैं n दोगुना से जुड़े सूचियों
• प्रत्येक सूची एक प्रहरी शुरुआत और अंत
है
• सूचियों में समान प्रारंभ और अंत नोड (आवश्यक नहीं है, लेकिन सादगी के लिए)
• सूचियां समरूप हैं और आइटम साझा कर सकती हैं

मैं सभी n सूचियों में अंत नोड, सभी नोड्स के एक आंशिक आदेश को खोजने के लिए, शुरुआत नोड के साथ शुरू और के साथ समाप्त, ठीक है, करना चाहते हैं इस तरह है कि किसी भी नोड जो NX सूचियों में प्रकट होता है , जहां x < n, सभी सूचियों में अन्य नोड्स के संबंध में सॉर्ट किया जाएगा जिसमें यह प्रतीत होता है।

सूचियों का एक उदाहरण सेट उपलब्ध कराने के लिए सरणियों का उपयोग करना:

first = [a, b, d, f, h, i]; 
second = [a, b, c,  f, g, i]; 
third = [a,   e, f, g, h, i]; 

जाहिर है, एक संभावित जवाब [, ए, बी, सी, डी, ई, एफ, जी, एच मैं] होगा, लेकिन एक और स्वीकार्य आदेश [ए, बी, डी, ई, सी, एफ, जी, एच, मैं] होगा।

मुझे पता है कि ऐसा करने के लिए एक तेज़ एल्गोरिदम है, क्या किसी को याद है कि यह कैसे जाता है या इसे क्या कहा जाता है? मेरे पास पहले से ही कुछ धीमे संस्करण हैं, लेकिन मुझे यकीन है कि कहीं नथ में कहीं तेज़ है।

(। और, इससे पहले आप से पूछना, इस होमवर्क या परियोजना यूलर के लिए नहीं है, और मैं इस किसी भी अधिक ठोस नहीं कर सकता यह समस्या है।)

संपादित करें: मुझे लगता है कि आंशिक अपेक्षाकृत यकीन ऑर्डरिंग केवल तभी परिभाषित की जाती है जब तक कि अंतराल सभी सूचियों में और उसी स्थिति में (शुरुआत और अंत) में हों। मैं उन अंतराल को खोजने के लिए एक रैखिक-समय की खोज के खिलाफ नहीं होगा, और यदि वे नहीं मिल पा रहे हैं, तो वहां एक त्रुटि उठाई जा सकती है।

Answer 1

मेरे लिए Topological sort जैसा दिखता है। आपको एक स्थलीय रूप से क्रमबद्ध राज्य प्राप्त करने के लिए कई एल्गोरिदम हैं। जिसे मैं विशेष रूप से पसंद करता हूं वह एक चौड़ाई पहली खोज के समान है। दो सूचियों को बनाए रखें, जिनमें सभी नोड्स हैं, जिनमें L (प्रारंभ में केवल a नोड), दूसरा आंशिक आदेशित नोड्स, F है।अब हर कदम,

pick a node from `L`, 
do some operations (explained later), 
and move the chosen node to the `F` list. 

"कुछ कार्य कर कदम" में, कम से

choose all successors of the source node which have exactly one in-link add them to L. 
Remove the link from the source node to all the successors in the previous step 

अब, सूची F अपने सभी नोड्स सांस्थितिकी अनुसार क्रमबद्ध हैं। मुझे भयानक स्पष्टीकरण के बारे में खेद है, विकी लिंक में अच्छे चित्र हैं :)

Answer 2

या तो मैं गलतफहमी कर रहा हूं, या एलियनहार्ड का एल्गोरिदम विफल हो सकता है। (मैं एक टिप्पणी के रूप में जोड़ना होगा, लेकिन मैं भी यहाँ नया टिप्पणी करने के लिए कर रहा हूँ।)

इस उदाहरण पर विचार:

first = [a, b, c, d,    i]; 
second = [a,  d, e, f,  i]; 
third = [a,    f, g, h, i]; 

Alienhard एल्गोरिथ्म दे देंगे: a=0, b=1, c=2, d=3, e=2, f=3, g=2, h=3, i=4।

एल्गोरिदम के बाद ए और आगे बढ़ने की आवश्यकता होती है, भले ही ई दूसरे में डी का पालन करता है।