Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Longest chain of elements from list in Python

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?

like image 966
fege Avatar asked May 11 '12 09:05

fege


People also ask

What is the maximum size of list in python?

According to the source code, the maximum size of a list is PY_SSIZE_T_MAX/sizeof(PyObject*) . On a regular 32bit system, this is (4294967295 / 2) / 4 or 536870912. Therefore the maximum size of a python list on a 32 bit system is 536,870,912 elements.

How do you find the longest word in a string python?

Iterate over the characters of the string. Check if the current character encountered is a space or end of the string is reached. If the current character is found to be so, update the maximum length of a word obtained. Finally, print the longest word obtained using substr() method.


4 Answers

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']
like image 125
Maria Zverina Avatar answered Oct 21 '22 13:10

Maria Zverina


Here are some comments:

  • you wish to return a path. So it is an ordered collection isn't it? You should probably not use a set for res, since set are unordered
  • do you know la length or the returned path? No you don't. So you might need a while somewhere
  • i.startswith(initial) is true only if i starts with the whole initial word. You probably don't want this
  • you try to use a recurcive approach. However you don't collect the result. The recurcive call is useless for the moment
  • nations is a global variable, which is bad

edit

The bug described in your comment may occur because your recurcive call is inside the j loop. The recurcive call may remove elements for the nations, which may also exist in initials. So you are trying to remove them more than once, which raises an exception. You probably mean to put chain(j) outside the loop (and maybe use its return value?)

like image 42
Simon Bergot Avatar answered Oct 21 '22 13:10

Simon Bergot


As a side note, your problem is NP-complete (meaning it has no "fast" polynomial-time solution.) It's solvable for small problem sizes, but it gets very difficult very quickly.

Your problem can be thought of as the longest-path problem on a directed graph.

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

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

Word DAG Example

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

This doesn't mean you can't do better than brute force. There's a dynamic programming algorithm that reduces the complexity from O(n!) (factorial, very bad) to O(n^2 * 2^n) (superexponential, still bad, but better than factorial.)

like image 2
Li-aung Yip Avatar answered Oct 21 '22 11:10

Li-aung Yip


this is a naive recursive approach... i feel like you could 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
like image 1
sobel Avatar answered Oct 21 '22 11:10

sobel