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

有什么建议吗？

- fege

---

它为何失效？ - Marcin

如果我保留nations.remove(j)，则会出现ValueError: list.remove(x): x not in list错误，如果我删除那段代码，则会出现RuntimeError: maximum recursion depth exceeded while calling a Python object。 - fege

请在您的问题中放置两个错误的完整堆栈跟踪，并使用注释标识涉及的代码行。 - Marcin

Answer 1

以下是一些评论：

• 您希望返回一个路径。因此它是有序集合，对吗？您可能不应该使用 set 来作为 res，因为 set 是无序的。
• 您知道返回的路径的长度吗？不知道。所以您可能需要在某个地方使用 while。
• i.startswith(initial) 只有在 i 以整个初始单词开头时才为真。您可能不想要这个。
• 您尝试使用递归的方法。但是您没有收集结果。目前来说，递归调用是无用的。
• nations 是一个全局变量，这是不好的。

编辑

您评论中描述的错误可能是由于您的递归调用在 j 循环内部。递归调用可能会删除 nations 中的元素，这些元素也可能存在于 initials 中。因此，您试图多次删除它们，这会引发异常。您可能希望将 chain(j) 放在循环外面（并且可能使用它的返回值？）

- Simon Bergot

Answer 2

我也选择了递归下降。不确定动态规划是否适用于此，因为列表在进行过程中被修改。稍微更紧凑，而且在调用 chain 之前不需要将 start 从列表中删除。 :-)

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

- Maria Zverina

Answer 3

作为一则附注，你的问题是NP完全问题（意味着没有“快速”的多项式时间解决方案）。它可以在小问题规模下得到解决，但随着问题规模增加，难度会迅速增加。

你的问题可以被视为有向图上的最长路径问题。

• 绘制一个有向图，其中每个单词（国家）表示为一个顶点。
• 对于每一对单词w1和w2，如果w1的最后一个字母与w2的第一个字母相同，则绘制边缘w1 -> w2。
• 如果w2的最后一个字母与w1的第一个字母相同，则还要绘制反向边缘从w2->w1。
• 找到包含最多顶点的最长路径（在这种情况下，“简单”意味着“不包括任何顶点超过一次”）。

这是一个水果和蔬菜列表的示例图：Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini。

这张图可能包含环（例如，这个图有一个循环：茄子 -> 橘子 -> 茄子 -> 橘子....）。因此，包含循环的有向图的最长路径问题是NP完全问题。因此，对于这个问题没有多项式时间的解决方案。 这并不意味着你不能做得更好。有一种动态规划算法可以将复杂度从O(n!)（阶乘，非常糟糕）降低到O(n^2 * 2^n)（超指数，仍然糟糕，但比阶乘好得多）。

- Li-aung Yip

Answer 4

这是一种天真的递归方法... 我感觉你可以使用动态规划，会更好。

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

- sobel

---

动态规划可以帮助你将时间复杂度从阶乘的 O(n!) 减少到类似于 O(n^2 * 2^n) 的程度，虽然仍然很糟糕，但比之前要好。总体问题是 NP 完全问题（见下文），这意味着“快速”算法不太可能存在。 - Li-aung Yip