più lunga catena di elementi di lista in Python

Question

ho una lista delle nazioni, e voglio avere il percorso più lungo delle nazioni in cui ogni paese scelto deve iniziare con la stessa lettera che si è conclusa l'elemento precedente

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

Ho provato in questo modo, ma non funziona

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 

Qualche suggerimento?

Answer 1

Sono partito anche per la discesa ricorsiva. Non sono sicuro che la programmazione dinamica sia adatta per questo dato che la lista viene modificata man mano che procediamo. Leggermente più compatto e non necessita di essere rimosso dall'elenco prima di chiamare la catena. :-)

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 

Chiama così. :-)

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

Answer 2

Ecco alcuni commenti:

• si desidera restituire un percorso. Quindi è una collezione ordinata, non è vero? Probabilmente non dovresti usare un set per res, dato che il set non è ordinato
• conosci la lunghezza o il percorso restituito? No, non lo fai. Quindi potresti aver bisogno di un while da qualche parte
• i.startswith(initial) è vero solo se inizio con l'intera parola iniziale. Probabilmente non vuoi che questo
• cerchi di utilizzare un approccio ricorsivo. Tuttavia non raccogli il risultato. La chiamata recurcive è inutile per il momento
• nations è una variabile globale, che è male

modificare

Il bug descritto nel tuo commento si può verificare perché la chiamata recurcive è all'interno del ciclo j . La chiamata ricurva può rimuovere elementi per le nazioni, che possono anche esistere nelle iniziali. Quindi stai provando a rimuoverli più di una volta, il che solleva un'eccezione. Probabilmente significa mettere chain(j) di fuori del ciclo (e magari utilizzare il suo valore di ritorno?)

Answer 3

questo è un approccio ricorsivo ingenuo ... Mi sento come si potrebbe usare programmazione dinamica e sarebbe meglio

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

Come nota a margine, il problema è NP-completo (il che significa che ha soluzione polinomiale "veloce".) E 'risolvibile per le piccole dimensioni del problema, ma diventa molto difficile, molto rapidamente.

Il tuo problema può essere considerato come il longest-path problem on a directed graph.

• Disegna a directed graph con ogni parola (paese) rappresentata come un vertice.
• Per ogni coppia di parole w1 e w2, disegnare un bordo w1 -> w2 se l'ultima lettera w1 è lo stesso della prima lettera del w2.
• Disegna anche il lato posteriore da w2->w1 se l'ultima lettera di w2 è la stessa della prima lettera di w1 s.
• Trova il maximum-length path - il percorso semplice che contiene il maggior numero di vertici. ("Semplice" in questo caso significa "che non includono alcun vertice più di una volta.")

Ecco un grafico di esempio per un elenco di frutta e verdura: Apple, banana, eggplant, kiwifruit, orange, oregano, tangerine, zucchini.

Questo grafico può contenere cicli (per esempio, questo grafico ha un ciclo eggplant -> tangerine -> eggplant -> tangerine..... The longest path problem for directed graphs containing cycles is NP-complete. Pertanto esiste una soluzione polinomiale per questo problema.

Questo non significa che si può' t fare meglio di forza bruta. There's a dynamic programming algorithm che riduce la complessità da O(n!) (fattoriale, molto pessimo) a O(n^2 * 2^n) (supere- sponenziale, ancora male, ma meglio fattoriale.)