最長在Python

從列表中的元素鏈我的國家的名單，我想有地方選擇的每個國家都必須與結束前一個元素相同字母開頭的國家的最長路徑最長在Python

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

有什麼建議嗎？

來源

2012-05-11 fege

我n它不起作用的方式是什麼？ – Marcin

如果我保留nations.remove（j），錯誤是ValueError：list.remove（x）：x不在列表中，如果我刪除了那段代碼RuntimeError：在調用Python對象時超出最大遞歸深度 – fege

請將完整堆棧跟蹤您的問題中的兩個錯誤，並使用註釋來標識所涉及的代碼行。 – Marcin

我也去了遞歸下降。不確定動態編程是否適合這一點，因爲列表在我們去的時候被修改了。稍微更緊湊，不需要在調用鏈之前從列表中刪除。 :-)

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']

來源

2012-05-11 10:25:42

這裏有一些評論：

您希望返回的路徑。所以這是一個有序的集合是不是？你可能不應該使用一組res，因爲set是無序的
你知道la的長度還是返回的路徑嗎？不，你不知道。所以你可能需要一個while某處
i.startswith(initial)只有當我以整個首字開始時纔是真的。你可能不希望這個
你嘗試使用一個反覆的方法。但是，您不會收集結果。該recurcive電話是沒用的時刻
nations是一個全局變量，這是壞

編輯

在您的評論，因爲你的recurcive呼叫j循環內，可能會出現所描述的錯誤。反覆呼叫可能會刪除這些國家的元素，這些元素也可能以縮寫形式存在。所以你試圖不止一次地刪除它們，這引發了一個例外。你大概的意思把chain(j)外循環（也許使用它的返回值？）

來源

2012-05-11 09:32:03 Simon

這是一個天真的遞歸方法......我覺得你可以使用動態規劃，這將是更好的

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

來源

2012-05-11 10:07:18 sobel

非常好的解決方案 – fege

動態編程可以幫助您將時間複雜度從「O（n！）」（階乘）降低到更像「O（n^2 * 2^n）」的東西，這仍然很糟糕，但*少*可怕。一般問題是NP完全（見下文），這意味着「快速」算法不太可能存在。 –

作爲一個側面說明，你的問題是NP完全性（這意味着它沒有「快」多項式時間的解決方案。）這是可解爲較小的問題大小，但它很快就變得非常困難。

您的問題可以被認爲是longest-path problem on a directed graph。

繪製一個directed graph與表示爲頂點的每個單詞（國家）。
對於每一個字對，並w1w2，繪製一個邊緣w1 -> w2如果w1最後一個字母是一樣的w2第一個字母。
如果w2的最後一個字母與w1的第一個字母相同，也從w2->w1中劃出反向邊緣。
查找maximum-length path - 包含最多頂點數的簡單路徑。（在這種情況下「簡單」的意思是「不多於一次包括任何頂點」。）

下面是水果和蔬菜清單的示例圖表：Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini。

Word DAG Example

該曲線圖可以含有周期（例如，該曲線圖中有一個循環eggplant -> tangerine -> eggplant -> tangerine....。The longest path problem for directed graphs containing cycles is NP-complete.因此，存在針對此問題沒有多項式時間的解決方案。

這並不意味着你不能做T比蠻力更好。There's a dynamic programming algorithm減少了從O(n!)複雜（階乘，非常壞）到O(n^2 * 2^n)（superexponential，仍然很糟糕，但比階乘更好。）

來源

2012-05-14 01:34:47

回答

相關問題