Longest chain of elements from list in Python
longest-path, python
Solution
I've also gone for recursive descent. Not sure if dynamic programming is a good fit for this as the list is modified as we go. Slightly more compact and doesn't need start removed from the list before calling chain. :-)
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
Call like this. :-)
>>> chain('spain', nations)
['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria']
Problem
I have a list of nations, and I want to have the longest path of nations where each country chosen must begin with the same letter that ended the previous element ``` 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'] ``` I tried this way, but it doesn't work ``` 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 ``` Any suggestion?