cadena más larga de los elementos de la lista en Python

Question

que tiene una lista de las naciones, y yo quiero tener la ruta más larga de las naciones donde cada país elegido debe comenzar con la misma letra que terminó el elemento anterior

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

Lo intenté de esta manera, pero no funciona

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 

¿Alguna sugerencia?

Answer 1

También he ido para el descenso recursivo. No estoy seguro de si la programación dinámica es adecuada para esto, ya que la lista se modifica a medida que avanzamos. Un poco más compacto y no necesita que se elimine de la lista antes de llamar a la cadena. :-)

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 

Llamada así. :-)

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

Answer 2

He aquí algunos comentarios:

• que desea devolver un camino. Entonces, es una colección ordenada, ¿no? Probablemente no deberías usar un conjunto para res, ya que set no está ordenado
• ¿conoces la longitud o la ruta devuelta? No, no lo haces. Por lo que es posible que necesite un while en algún lugar
• i.startswith(initial) es verdadero solo si comienzo con la palabra inicial completa. Probablemente no desee que
• trate de utilizar un enfoque recurrente. Sin embargo, no recolectas el resultado. La llamada recurcive es inútil por el momento
• nations es una variable global, lo cual es malo

edición

El error se describe en puede ocurrir debido a su llamada recurcive está dentro del bucle j su comentario . La llamada recurrente puede eliminar elementos de las naciones, que también pueden existir en las iniciales. Por lo tanto, intenta eliminarlos más de una vez, lo que genera una excepción. Es probable que decir para poner chain(j) fuera del bucle (y tal vez usar su valor de retorno?)

Answer 3

Este es un enfoque recursivo ingenua ... me siento como usted podría utilizar la programación dinámica y sería mejor

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

Como nota al margen, el problema es NP-completo (lo que significa que no tiene solución en tiempo polinómico "rápida".) Es solucionable para tamaños pequeños problemas, pero se hace muy difícil muy rápidamente.

Su problema se puede considerar como longest-path problem on a directed graph.

• Dibuja un directed graph con cada palabra (país) representada como un vértice.
• Por cada par de palabras, w1 y w2, dibujar un borde w1 -> w2 si la última letra de w1 es la misma que la primera letra del w2.
• También dibuje el reverso de w2->w1 si la última letra de w2 es igual a la primera letra de w1.
• Encuentra maximum-length path - la ruta simple que contiene la mayor cantidad de vértices. ("Simple" en este caso significa "sin incluir cualquier vértice más de una vez.")

He aquí un gráfico de ejemplo de una lista de frutas y verduras: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini.

Este gráfico puede contener ciclos (por ejemplo, esta gráfica tiene un ciclo eggplant -> tangerine -> eggplant -> tangerine..... The longest path problem for directed graphs containing cycles is NP-complete. Por lo tanto no hay ninguna solución en tiempo polinómico para este problema.

Esto no significa que usted puede' t hacen mejor que la fuerza bruta. There's a dynamic programming algorithm que reduce la complejidad de O(n!) (factorial, muy malo) a O(n^2 * 2^n) (superexponential, siendo malo, pero mejor que factorial.)