हैशिंग के साथ पथ पुनर्निर्माण?

Question

मैं जावा में निम्नलिखित हल करने के लिए एक हे (एन) समय जटिलता एल्गोरिथ्म लगाने के लिए कैसे पता लगाने की कोशिश कर रहा है:

हम एक प्रारंभ बिंदु और अंत बिंदु के साथ एक इनपुट जोड़ी दिया जाता है, और हम ऐसी है कि एक इनपुट की शुरुआत (इस मामले में वर्णानुक्रम) अन्य इनपुट के अंत से मेल खाता है एक पथ का निर्माण करने के

पूर्व है: अगर मैं एक सूची

पंजाब
बी.एम.
ओपी ०१२३८००७३१६ है MZ

जहां पंजाब, या बी.एम. जोड़े हैं, पी प्रारंभ बिंदु जा रहा है और बी अंत

जा रहा है मैं

ओपी
पंजाब
बी.एम.
आउटपुट के रूप में बनाना चाहिए एमजेड

और स्वाभाविक रूप से, मैं चाहता हूं चक्र की जांच करने के लिए - इस मामले में मैं सिर्फ एक चक्र होने पर रिपोर्ट करूंगा।

पहली बार मैंने ऐसा करने की कोशिश की, मैंने एक स्वैपिंग एल्गोरिदम का उपयोग किया जो ओ (एन^2) था, मूल रूप से दो प्रविष्टियों को स्वैप करके यदि सूची थी और सूची को नीचे ले जाया गया था। ऐसा करने का एक तेज़ तरीका है, और मैं समझता हूं कि इसे कैसे करना है, लेकिन मैं सोच रहा था कि कोई इसे थोड़ा साफ़ कर सकता है या नहीं।

असल में, मुझे लगता है कि आपको कुछ प्रकार की हैश/कुंजी प्रकार की संरचना बनाने की आवश्यकता है, जहां आप किसी कुंजी द्वारा ऑब्जेक्ट के मान को संदर्भित कर सकते हैं।

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

मेरी एकमात्र चीज यह है कि, मैं हैश तालिका या कुछ समान डेटा संरचना का उपयोग करके जावा में इसे कार्यान्वित करने का बिल्कुल सही नहीं समझ सकता। क्या मुझे हैश टेबल को अलग करने के लिए स्टार्ट और सिरों को जोड़ना है और फिर लुकअप कुंजियों के रूप में प्रारंभ बिंदुओं का उपयोग करना है? कोई है जो GitHub पर अजगर में इसे हल में देखने से

स्यूडोकोड:

for inputs 
    parse input 
    add parse[1] to starts, add parse[2] to ends 

for starts 
    find origin (a start not in ends) <--requires hash? 

if no origin 
    cycle exists 

for inputs 
    find ends[origin] <--requires hash? 
    origin = ends[origin] <-- so we can find the next one 

अगर कोई मेरी मदद कर सकता जावा में एक एल्गोरिथ्म (करने के लिए इस का अनुवाद सोच अन्य कुशल समाधान बहुत स्वागत के बाद से मैं इस में दिलचस्पी रखता हूँ समस्या निवारण का प्रकार) या डेटा संरचना परिप्रेक्ष्य से इसे अधिक सामान्य रूप से समझना।

String[][] paths = { 
     {"P", "B"}, 
     {"B", "M"}, 
     {"O", "P"}, 
     {"M", "Z"}, 
    }; 

    // create a single hash map, mapping start->end 
    HashMap<String, String> end = new HashMap<>(); 

    for(int i = 0; i < paths.length; i++) 
    { 
     end.put(paths[i][0], paths[i][1]); 
    } 

    // find if a cycle exists 
    String origin = null; 
    for (String key : end.keySet()) { 
     if(!end.containsValue(key)) 
     { 
      origin = key; 
      break; 
     } 
    } 

    if(origin == null) 
    { 
     System.out.println("cycle exists"); 
     return; // no origin found, cycle exists 
    } 

    // iterate over hash map: 
    int count = 0; 
    while(true) 
    { 
     if(!end.containsKey(origin)) 
      break; 
     String next = end.get(origin); 
     System.out.println(origin + " " + next); 
     origin = next; 
     if(++count > paths.length) 
     { 
      System.out.println("cycle exists"); 
      break; 
     } 
    } 

end भंडार अंत बिंदु (मान) को देखते हुए प्रारंभ बिंदु (key):

Answer 1

यहाँ जावा में HashMaps का उपयोग कर एक सरल कार्यान्वयन है।

यदि कोई बिंदु प्रारंभ बिंदु के रूप में मौजूद है लेकिन अंत बिंदु नहीं है तो यह end में एक कुंजी होगी लेकिन end में कोई मान नहीं है। तो end की कीसेट पर फिर से चल रहा है और end की जांच कर रहा है, तो प्रत्येक कुंजी को एक मूल के रूप में एक मूल के रूप में शामिल किया जाएगा। यदि ऐसी कोई उत्पत्ति नहीं है तो एक चक्र है। हालांकि, यह निर्धारित करने के लिए पर्याप्त नहीं है कि कोई चक्र है या नहीं, क्योंकि मूल होने पर भी चक्र हो सकता है। इस सेट पर विचार करें:

P B 
B M 
O P 
M Z 
Z M 

वहाँ एक अद्वितीय मूल (ओ) है, लेकिन वहाँ भी एक चक्र एम है -> जेड -> एम यह पता लगाने के लिए आप सेट चलना और ट्रैक जिनमें से बात आपके पास पहले से रख सकते हैं दौरा किया, या अधिक आसानी से आप सेट चल सकते हैं और यदि आप इनपुट की लंबाई से अधिक अंक का दौरा करते हैं तो एक चक्र होना चाहिए।

सेट पर चलने के लिए, मूल पर एक स्ट्रिंग सेट करें। फिर end में origin को कुंजी के रूप में मान को देखते रहें, और प्रारंभ, अंत के रूप में कुंजी, मूल्य जोड़ी (मूल, end.get (मूल)) प्रिंट करें। फिर end.get (मूल) को नई उत्पत्ति के रूप में सेट करें। लूप समाप्त होता है जब वर्तमान उत्पत्ति के अंत में हैश मैप में कोई मूल्य नहीं मिलता है।

इस एल्गोरिथ्म में विफल रहता है, अगर वहाँ सूची में डुप्लिकेट आरंभ या अंत पदों कर रहे हैं, उदाहरण के लिए:

P B 
B M 
O P 
M Z 
B Z 

यह सवाल से स्पष्ट नहीं है कि आप इस मामले को संभालने के लिए है।

Answer 2

हालांकि मैं तरह

class Node { 
    String name; 
    Node prev; 
    Node next; 
} 

केवल

यह अभी भी संभव है मानचित्र के साथ यह करने के लिए (HashMap अगर आप चाहते हैं) कुछ के साथ संरचना की तरह किसी लिंक किए गए-सूची को पसंद करेंगे।

यह सिर्फ कुछ गुर अपने कोड में कम लग रहा है कर सकते हैं कि के साथ, @samgak से जवाब के समान दिखता है (आवश्यक नहीं तेजी से, यह बेंचमार्क नहीं किया है):

String[][] rawPaths = { 
    {"P", "B"}, 
    {"B", "M"}, 
    {"O", "P"}, 
    {"M", "Z"}, 
}; 


// 1. You can keep only one `Map<String, String> which keeps start as key and end as value. 

Map<String, String> pathMap = new HashMap<>(); 
for (String[] path : rawPaths) { 
    pathMap.put(path[0], path[1]); 
} 

// 2. Some validity checks for data: 

// 2.1 No of entry in final Map should equals to number of lines in raw data, which means there is no duplicated "start" node. 
assert pathMap.size() == rawPaths.length; 

// 2.2 There should be no duplicate in "end", i.e. no partial cyclic path 
assert new HashSet<>(pathMap.values()).size() == rawPaths.length; 

// 2.3 there should be one and only one start value that does not exists in end values, i.e. no full cyclic path 
Set<String> startPoints = new HashSet<>(pathMap.keySet()); 
startPoints.removeAll(pathMap.values()); 

assert startPoints.size() == 1; 

//3. Then you can make up the path by getting the "head" which is the only value left in startPoints, and construct the full path 

String start= startPoints.iterator().next(); 

while (pathMap.contains(start)) { 
    String end = pathMap.get(start); 
    System.out.println(start + " " + end); 
    start = end; 
} 

अभी भी मामलों हो सकता है कि वहाँ इस तरह चक्रीय द्वीप मार्ग है:

A B 
B C 
C D 
X Y 
Y X 

कि आसानी से, तुम्हारे जाने के बाद भाग 3 के माध्यम से चल, एक काउंटर रखने के लिए और काउंटर अंत में pathMap.size() के समान होना चाहिए जाँच की जा सकती। यदि नहीं, तो चक्रीय द्वीप