Наибольшая цепь элементов из списка в Python

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 вызов внутри J цикла , Повторяющийся вызов может удалять элементы для стран, которые могут также существовать в инициалах. Поэтому вы пытаетесь удалить их более одного раза, что вызывает исключение. Вы, вероятно, означает поставить 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

Как примечание стороны, ваша проблема NP-полной (то есть он не имеет «быстрый» полиномиальное время решения). Это решаемая для небольших размеров проблемы, но это становится очень трудно очень быстро.

Ваша проблема может быть охарактеризована как longest-path problem on a directed graph.

• Нарисуйте directed graph с каждым словом (страной), представленным в виде вершины.
• Для каждой пары слов, w1 и w2, рисовать края w1 -> w2 если последняя буква w1 таких же, как первая буква w2.
• Также нарисовать обратный край от w2->w1, если w2 s последнее письмо совпадает с 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. Поэтому нет полиномиального времени решения этой проблемы.

Это не означает, что вы можете» т лучше, чем грубая сила. There's a dynamic programming algorithm, что уменьшает сложность от O(n!) (факториала, очень плохо) до O(n^2 * 2^n) (сверхэкспоненциальный, по-прежнему плохо, но лучше, чем факториал.)