Migliore equivalente di questo pazzo nested python per loop

for a in map: 
    for b in map[a]: 
     for c in map[b]: 
      for d in map[c]: 
       for e in map[d]: 
        print a+b+c+d+e

Il codice precedente viene utilizzato per creare tutti i percorsi di una certa lunghezza in un grafico. mappa [a] rappresenta i punti che puoi raggiungere dal punto a.Migliore equivalente di questo pazzo nested python per loop

Come posso modificarlo per simulare un numero arbitrario di loop?

Questo è come un prodotto cartesiano (itertools.product) dove ad ogni iterazione la scelta per l'elemento successivo è limitata a quelli nella mappa [punto corrente].

fonte

2012-01-18 Babak

Bene, avete etichettato con ricorsione .. hai provato questo? – wim

map = { 
    'a': ['b', 'c'], 
    'b': ['c', 'd'], 
    'c': ['d', 'a'], 
    'd': [] 
} 

def print_paths(map, start, length, prefix = ''): 
    if length == 0: 
     print prefix 
    else: 
     for a in map[start]: 
      print_paths(map, a, length - 1, prefix + start) 

for a in map.keys(): 
    print_paths(map, a, 5)

fonte

2012-01-18 07:09:44

Mi dispiace aver dimenticato di menzionare la mappa [a] [b] è un numero intero che rappresenta la distanza tra a a b. Quindi la tua soluzione smette di funzionare non appena raggiunge il numero intero. Puoi dirmi come cambiarlo in un equivalente esatto del ciclo annidato? Quindi la funzione non va oltre la mappa [a]. (la mappa [X] è sufficiente per ogni punto X dato che la tua scelta su dove andare dopo un certo punto non dipende da come sei arrivato) – Babak

Se map [a] [b] è un numero intero, il tuo originale il codice non può funzionare. Potresti aggiornare la domanda con un esempio funzionante di 'map'? Aggiungerò il tipo di 'mappa' che ho assunto per questa risposta. –

... e modifica la risposta per funzionare davvero, poiché né io né i 5 upvoters abbiamo notato che non funzionava ... –

Questo è un classico problema ricorsivo. La funzione deve restituire la concatenazione del valore del nodo con tutti i risultati della funzione della funzione per ciascun nodo figlio. Come si può vedere nella sentenza, il comportamento funzione viene spiegata in modo ricorsivo:

myGraph = { 1:[2,3], 2:[3,4] } 

def recorre(node_list, p = ''):  
    for node in node_list: 
     if node in myGraph and myGraph[node]: 
      recorre(myGraph[node], p+unicode(node)) 
     else: 
      print p+unicode(node) 

recorre(myGraph)

Risultato:

>>> recorre(myGraph) 
123 
124 
13 
23 
24

Questo codice è un punto di partenza. È possibile memorizzare tutti i percorsi in un elenco, utilizzare il generatore yield, ecc. Non dimenticare di evitare le cerchie.

Inoltre, dare un'occhiata a igraph solution. Sicuramente questa libreria può aiutarti, vedi questo esempio: Finds all shortest paths (geodesics) from a vertex to all other vertices.

Saluti.

fonte

2012-01-18 08:22:36 danihp

Proprio come altri hanno suggerito, con la ricorsione:

distances = []   

    def compute_distance(map, depth, sum): 
     if depth == 0 or len(map) == 0: 
      distances.append[sum] 
     else: 
      for a in map: 
       compute_distance(map[a], depth - 1, sum + a) 

    compute_distance(map, x, 0)

fonte

2012-01-18 10:50:59 Bogdan

Migliore equivalente di questo pazzo nested python per loop

risposta

Problemi correlati