Вопрос по python – Самая длинная цепочка элементов из списка в Python

6

У меня есть список наций, и я хочу иметь самый длинный путь наций, где каждая выбранная страна должна начинаться с той же буквы, что и предыдущий элемент

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

Я пробовал таким образом, но это не работает

<code>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
</code>

Любое предложение?

Как это не работает? Marcin
если я оставлял Nations.remove (j), ошибка будет ValueError: list.remove (x): x нет в списке, если я удалю этот фрагмент кода RuntimeError: максимальная глубина рекурсии превышена при вызове объекта Python fege
Пожалуйста, поместите полные трассировки стека для обеих ошибок в вашем вопросе, и используйте комментарий, чтобы определить строку кода. Marcin

Ваш Ответ

4   ответа
1

это наивный рекурсивный подход ... я чувствую, что вы могли бы использовать динамическое программирование, и было бы лучше

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
Динамическое программирование может помочь вам уменьшить сложность времени сO(n!) (факториал) к чему-то более похожемуO(n^2 * 2^n), который все еще ужасен, ноless ужасно. Общая проблема является NP-полной (см. Ниже), что означает «быстро» алгоритмы вряд ли существуют.
очень приятно это решение fege
2

Напомним, что ваша проблема является NP-полной (то есть она не имеет «быстрого» решения за полиномиальное время). Она разрешима для задач небольшого размера, но очень быстро становится очень трудной.

Ваша проблема может рассматриваться какзадача с наибольшим путем на ориентированном графе.

  • Draw a directed graph with each word (country) represented as a vertex.
  • For every pair of words, w1 and w2, draw an edge w1 -> w2 if the last letter of w1 is the same as the first letter of w2.
  • Also draw the reverse edge from w2->w1 if w2s last letter is the same as w1s first letter.
  • Find the maximum-length path - the simple path containing the most number of vertices. ("simple" in this case means "not including any vertex more than once.")

Вот пример графика списка фруктов и овощей:Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini.

Word DAG Example

Этот график может содержать циклы (например, этот график имеет циклeggplant -> tangerine -> eggplant -> tangerine..... Самая длинная задача о пути для ориентированных графов, содержащих циклы, является NP-полной. Поэтому для этой проблемы нет решения за полиномиальное время.

Это не означает, что вы не можете добиться большего успеха, чем грубая сила.Там алгоритм динамического программирования что уменьшает сложность отO(n!) (факториал,very плохо) чтобыO(n^2 * 2^n) (суперэкспоненциальный, все еще плохой, но лучше факториального.)

5

Я также пошел на рекурсивный спуск. Не уверен, подходит ли для этого динамическое программирование, поскольку список изменяется по мере продвижения. Чуть более компактный и не нужно начинать удалять из списка перед вызовом цепочки. :-)

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

Вот несколько комментариев:

  • you wish to return a path. So it is an ordered collection isn't it? You should probably not use a set for res, since set are unordered
  • do you know la length or the returned path? No you don't. So you might need a while somewhere
  • i.startswith(initial) is true only if i starts with the whole initial word. You probably don't want this
  • you try to use a recurcive approach. However you don't collect the result. The recurcive call is useless for the moment
  • nations is a global variable, which is bad

edit

Ошибка, описанная в вашем комментарии, может возникнуть из-за того, что ваш рекурсивный вызов находится внутри цикла j. Рекурсивный вызов может удалить элементы для наций, которые могут также существовать в инициалах. Таким образом, вы пытаетесь удалить их более одного раза, что вызывает исключение. Вы, вероятно, хотите поставитьchain(j) вне цикла (и, возможно, использовать его возвращаемое значение?)

Похожие вопросы