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

我试过这样做，但没用

^{pr2}$

有什么建议吗？在

Answer 1

顺便说一句，你的问题是NP完全的（这意味着它没有“快速”的多项式时间解），它对于小问题是可以解决的，但是它很快就会变得非常困难。在

你的问题可以看作是longest-path problem on a directed graph。在

• 画一个directed graph，每个单词（国家）表示为一个顶点。在
• 对于每对单词w1和w2，如果w1的最后一个字母与w2的第一个字母相同，则画一条边w1 -> w2。在
• 如果w2->w1的最后一个字母与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.因此这个问题没有多项式时间解。在

这并不意味着你不能比暴力做得更好。There's a dynamic programming algorithm，它将复杂度从O(n!)（阶乘，非常bad）降低到{}（超指数，仍然不好，但比阶乘好）

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

像这样打电话。：-）

^{pr2}$

Answer 3

以下是一些评论：

• 您希望返回一条路径。所以这是一个有序的集合，不是吗？您可能不应该将集合用于res，因为集合是无序的
• 你知道拉长还是返回路径？不，你不需要。所以你可能需要一个while
• i.startswith(initial)只有当我以整个初始单词开头时才是真的。你可能不想要这个
• 你试着用一种康复的方法。但是你不收集结果。恢复呼叫暂时没有用
• nations是一个全局变量，这是错误的

编辑

您的注释中描述的bug可能是因为您的递归调用在j循环中。复健性的呼唤可以消除民族的元素，这些元素也可能存在于首字母中。因此，您试图多次删除它们，这引发了一个异常。您可能是想把chain(j)放在循环之外（也许还要使用它的返回值？）在