अजगर

Question

में सूची से तत्वों की सबसे लंबी श्रृंखला मैं देशों की एक सूची है, और मैं राष्ट्रों के सबसे लंबे समय तक पथ जहां प्रत्येक देश चयनित इसी पत्र है कि पिछले तत्व समाप्त हो गया से आरंभ होने चाहिए करना चाहते हैं

nations = ['albania','andorra','austria','belarus','belgium','bosnia and herzegovina', 
     'bulgaria','croatia','czech republic','denmark','estonia', 
     'finland','france','germany','greece','hungary', 
     'iceland','ireland','italy','latvia','liechtenstein','lithuania','luxembourg', 
     'macedonia','malta','moldova','monaco','montenegro','netherlands', 
     'norway','poland','portugal','romania','russia', 
     'san marino','serbia','slovakia','slovenia','spain','sweden', 'switzerland', 
     'ukraine','united kingdom','vatican city'] 

chain('spain') 
>>>['spain', 'netherlands', 'slovenia', 'andorra', 'austria', 'albania'] 

मैंने इस तरह से कोशिश की, लेकिन यह

def chain(naz): 
    initial = naz[-1] 
    initials=[] 
    res = set() 
    res.add(naz) 
    for i in nations: 
     if i.startswith(initial): 
      initials.append(i) 
    for j in initials: 
     nations.remove(j) 
     res.add(j) 
     chain(j) 
    return res 

कोई सुझाव नहीं है?

Answer 1

मैं भी रिकर्सिव वंश के लिए चला गया है। निश्चित नहीं है कि गतिशील प्रोग्रामिंग इसके लिए एक अच्छा फिट है क्योंकि सूची के रूप में संशोधित किया गया है। थोड़ा अधिक कॉम्पैक्ट और कॉलिंग श्रृंखला से पहले सूची से हटाए जाने की आवश्यकता नहीं है। :-)

def chain(start, countries): 
    remaining = list(countries) 
    del remaining[remaining.index(start)] 
    possibles = [x for x in remaining if x[:1] == start[-1:]] 
    maxchain = [] 
    for c in possibles: 
     l = chain(c, remaining) 
     if len(l) > len(maxchain): 
      maxchain = l 
    return [start] + maxchain 

इस तरह कॉल करें। (अर्थात यह कोई "तेज" बहुपद समय समाधान है।) :-)

>>> chain('spain', nations) 
['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria'] 

Answer 2

यहाँ कुछ टिप्पणियां कर रहे हैं:

• आप एक रास्ता वापस लौटना चाहते हैं। तो यह एक आदेश दिया गया संग्रह है ना? आपको शायद res के लिए सेट का उपयोग नहीं करना चाहिए, क्योंकि सेट अनॉर्डर्ड
• क्या आप ला लंबाई या लौटा पथ जानते हैं? नहीं तुम नहीं करते तो आपको while कहीं
• i.startswith(initial) केवल तभी सत्य होगा जब मैं पूरे प्रारंभिक शब्द से शुरू होता हूं। आप शायद यह
• नहीं चाहते हैं कि आप एक पुनरावर्ती दृष्टिकोण का उपयोग करने का प्रयास करें। हालांकि आप परिणाम एकत्र नहीं करते हैं। recurcive कॉल पल के लिए बेकार है
• nations है एक वैश्विक चर, जो बुरा है

संपादित

बग अपनी टिप्पणी हो सकती है क्योंकि आपके recurcive कॉल जे लूप के अंदर है में वर्णित । आवर्ती कॉल राष्ट्रों के लिए तत्वों को हटा सकती है, जो प्रारंभिक में भी मौजूद हो सकती हैं। तो आप उन्हें एक से अधिक बार हटाने की कोशिश कर रहे हैं, जो अपवाद उठाता है। आप शायद पाश बाहर chain(j) डाल करने के लिए मतलब है (और शायद का उपयोग अपनी वापसी मान?)

Answer 3

यह एक अनुभवहीन पुनरावर्ती दृष्टिकोण है ... मुझे लगता है आप गतिशील प्रोग्रामिंग इस्तेमाल कर सकते हैं और यह बेहतर होगा की तरह

def chain(start,options): 
    #start is the starting word 
    #options are the words left 

    next_options = [country for country in options if country[0] == start[-1]] 

    #if theres no options, return the single 
    if not next_options: 
     return [start] 

    #otherwise, return best chain out of the next option 
    best_chain = None 
    longest_chain = 0 

    for option in next_options: 

     new_options = options[:] 
     new_options.remove(option) 

     possible_chain = chain(option,new_options) 

     if len(possible_chain) > longest_chain: 
      best_chain = possible_chain 
      longest_chain = len(possible_chain) 

    return [start] + best_chain 

Answer 4

एक तरफ ध्यान दें के रूप में, आपकी समस्या एनपी पूरा हो गया है यह छोटी सी समस्या आकार के लिए व्याख्या करने योग्य है, लेकिन यह बहुत जल्दी बहुत मुश्किल हो जाता है।

आपकी समस्या को longest-path problem on a directed graph के रूप में सोचा जा सकता है।

• प्रत्येक शब्द (देश) के साथ एक directed graph ड्रा एक शीर्ष के रूप में प्रतिनिधित्व।
• शब्द के हर जोड़ी के लिए, w1 और w2, बढ़त w1 -> w2 आकर्षित करता है, तो w1 के अंतिम पत्र w2 के पहले अक्षर के समान है।
• w2->w1 से रिवर्स एज भी खींचें यदि w2 का अंतिम अक्षर w1 के पहले अक्षर जैसा ही है।
• maximum-length path खोजें - सरल पथ जिसमें सबसे अधिक शिखर होते हैं। ("सरल" इस मामले में अर्थ है "किसी भी एक से अधिक बार शिखर शामिल नहीं है।")

यहाँ फल और सब्जियों की एक सूची के लिए एक उदाहरण ग्राफ है: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini।

यह ग्राफ चक्र हो सकती है (उदाहरण के लिए, यह ग्राफ एक चक्र है eggplant -> tangerine -> eggplant -> tangerine....। The longest path problem for directed graphs containing cycles is NP-complete. इसलिए इस समस्या के लिए कोई बहुपद समय समाधान है।

यह आपको मतलब यह नहीं है यह कर सकते हैं ' टी जानवर बल की तुलना में बेहतर O(n^2 * 2^n) को (superexponential बुरा, अभी भी है, लेकिन भाज्य की तुलना में बेहतर।) है। There's a dynamic programming algorithm कि O(n!) से जटिलता को कम (भाज्य, बहुत बुरा)