The longest chain of items from a list in Python

Question

I have a list of nations, and I want to have the longest path of peoples, where each selected country should begin with the same letter that completed 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 does not 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?

Answer 1

I also went on a recursive descent. Not sure if dynamic programming is suitable for this, as the list changes as you go. A little more compact and no need to start deleting from the list before calling the 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 it. :-)

 >>> chain('spain', nations) ['spain', 'netherlands', 'serbia', 'albania', 'andorra', 'austria'] 

Answer 2

Here are some comments:

• you want to return the path. So what is an ordered collection? You should probably not use the set for res, since the set is unordered
• Do you know the length or return path? No no. So you may need a while somewhere
• i.startswith(initial) true only if I start with the whole initial word. You probably don't want this.
• You are trying to use a recursive approach. However, you will not get the result. A recuperative call is currently useless
• nations is a global variable that is bad

change

The error described in your comment may occur because your recurcive call is inside the j-loop. A repeated call may delete items for countries that may also exist in the initials. Therefore, you try to delete them more than once, which raises an exception. You probably want to put chain(j) outside the loop (and perhaps use its return value?)

Answer 3

As a side note, your problem is NP-complete (meaning that it does not have a “quick” solution with polynomial time.) It is solvable for small problem sizes, but it becomes very difficult very quickly.

Your problem can be seen as a long-path problem on a directed graph .

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

Here is an example chart for a list of fruits and vegetables: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini .

This graph may contain cycles (for example, this graph has the cycle eggplant -> tangerine -> eggplant -> tangerine.... The longest path problem for directed graphs containing loops is NP-complete. Therefore, there is no solution to this problem polynomial time solutions.

This does not mean that you cannot do better than brute force. There is a dynamic programming algorithm that reduces complexity from O(n!) (Factorial, very bad) to O(n^2 * 2^n) (superexponential, still bad, but better than factorial.)

Answer 4

this is a naive recursive approach ... I feel like you can use dynamic programming and it would be better

 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