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

以下是一些评论:

• 你希望回归一条路.所以它是一个有序的集合不是吗？您可能不应该为res使用set,因为set是无序的
• 你知道la length还是返回的路径？不,你没有.所以你可能需要while某个地方
• i.startswith(initial)只有当我从整个初始单词开始时才是真的.你可能不想要这个
• 你尝试使用recurcive方法.但是,您不收集结果.此刻的重复呼叫毫无用处
• nations 是一个全局变量,这是坏事

编辑

您的评论中描述的错误可能会发生,因为您的recurcive调用在j循环内.重复呼叫可以删除国家的元素,这些元素也可能存在于首字母中.所以你试图不止一次地删除它们,这引起了一个例外.你可能意味着把它放在chain(j)循环之外(并且可能使用它的返回值？)

Answer 2

我也去了递归下降.不确定动态编程是否适合这种情况,因为列表会随着我们的进行修改.稍微更紧凑,在调用链之前不需要从列表中删除.:-)

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