chaîne la plus longue d'éléments de la liste en Python

Question

J'ai une liste des nations, et je veux avoir le plus long chemin des nations où chaque pays choisi doit commencer par la même lettre qui a mis fin l'élément précédent

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

J'ai essayé de cette façon, mais cela ne fonctionne pas

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 

Une suggestion?

Answer 1

Je suis également allé pour une descente récursive. Je ne sais pas si la programmation dynamique convient bien à cette situation, car la liste est modifiée au fur et à mesure. Légèrement plus compact et n'a pas besoin d'être retiré de la liste avant d'appeler la chaîne. :-)

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 

Appelez comme ceci. :-)

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

Answer 2

Voici quelques commentaires:

• vous souhaitez retourner un chemin. Donc c'est une collection ordonnée n'est-ce pas? Vous ne devriez probablement pas utiliser un ensemble pour res, puisque les ensembles sont non ordonnés.
• connaissez-vous la longueur ou le chemin retourné? Non, vous ne le faites pas. Donc vous pourriez avoir besoin d'un while quelque part
• i.startswith(initial) est vrai seulement si je commence par le mot initial entier. Vous ne voulez probablement pas ce
• vous essayez d'utiliser une approche récurrente. Cependant, vous ne collectez pas le résultat. L'appel recurcive est inutile pour l'instant
• nations est une variable globale, ce qui est mauvais

modifier

Le bogue décrit dans votre commentaire peut se produire parce que votre appel recurcive est dans la boucle j . L'appel récurrent peut supprimer des éléments pour les nations, qui peuvent également exister en initiales. Donc, vous essayez de les supprimer plus d'une fois, ce qui soulève une exception. Vous voulez dire probablement mettre chain(j) en dehors de la boucle (et peut-être utiliser la valeur de retour?)

Answer 3

ceci est une approche récursive naïve ... je sens que vous pouvez utiliser la programmation dynamique et il serait préférable

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 

Answer 4

Comme une note de côté, votre problème est NP-complet (ce qui signifie qu'il n'a pas de solution polynomiale-temps « rapide ».) Il est résoluble pour la petite taille des problèmes, mais il est très difficile très rapidement. Votre problème peut être considéré comme longest-path problem on a directed graph.

• Dessiner un directed graph avec chaque mot (pays), représenté comme un sommet.
• Pour chaque paire de mots, w1 et w2, tirer un avantage w1 -> w2 si la dernière lettre de w1 est le même que la première lettre de w2.
• Dessinez également le bord inverse de w2->w1 si la dernière lettre de w2 est la même que la première lettre de w1 s.
• Trouvez le maximum-length path - le chemin simple contenant le plus grand nombre de sommets. (« Simple » dans ce cas signifie « ne comprenant pas un sommet plus d'une fois. »)

Voici un exemple de graphique pour une liste de fruits et légumes: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini.

Ce graphique peut contenir des cycles (par exemple, ce graphique a un cycle eggplant -> tangerine -> eggplant -> tangerine..... The longest path problem for directed graphs containing cycles is NP-complete. Par conséquent, il n'y a pas de solution polynomial pour ce problème.

Cela ne signifie pas que vous pouvez » t faire mieux que la force brute. There's a dynamic programming algorithm qui réduit la complexité de O(n!) (factoriel, très mauvais) à O(n^2 * 2^n) (superexponentielle, encore mal, mais mieux que factoriel.)