[Python] Cosa fà con questa istruzione?

[e-commerce84]

Ciao,
il professore usa Python per gli algoritmi del corso di algoritmi e strutture dati ma non avendo mai avuto esperienza diretta con questo linguaggio ho qualche difficoltà a capire cosa fà questa istruzione:


d = [[[V for u in V] for v in V] for k in range (-1 , n)]


In pratica che stà facendo?

Grazie
Andrea

[cdimauro]

Devi dire al tuo professore che le list comprehension (si chiamano così le espressioni fra parentesi quadre) devono essere comprensibili. :D

Nello specifico, leggendo dalla più esterna alla più interna, viene creata una lista di n + 1 elementi (avrebbe potuto scrivere range(0, n + 1): sarebbe stato più comprensibile! A meno che non si tratti di un esame, e allora avrei scelto anche di peggio :asd:).

Ogni elemento di questa lista è costituito a sua volta da una lista (quella "di mezzo"), con un numero di elementi pari a quelli contenuti nel vettore V.

A sua volta, quest'ultima lista è costituita da una lista (quella più interna) con un numero di elementi pari a quelli... contenuti nel vettore V. :D

Con un esempio si capisce meglio:
>>> V = [0, 1, 2, 3]
>>> n = 10
>>> d = [[[V for u in V] for v in V] for k in range (-1 , n)]
>>> d
0: [[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]],
[[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]],
[[0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3], [0, 1, 2, 3]]]]

[e-commerce84]

Ciao,
intanto mille grazie
no non si tratta di un esame ma fà parte del listato dell'algoritmo di Floyd-Roy-Warshall che risolve il problema dell'All Pairs Shortest Path (dato un grafo G, calcola i cammini minimi tra tutte le coppie di nodi)

Mi sono però appena accorto però di aver scritto una cavolata, facendo copia e incolla dal PDF delle dispense un carattere si è sminchiato e da simbolo matematico di infinito è diventato V.

In realtà volevo scrivere:


n = len(G) # n contiene il NUMERO DI NODI in G
V = range(n) # V è l'insieme dei noidi del grafo G che sono ordinati da 0 ad n


D = [[[INFINITO for u in V] for v in V] for k in range(-1, n)] # D è la MATRICE DELLE DISTANZE TRA 2 NODI u e v al PASSO k


Vediamo però se ho capito bene il tuo ragionamento:
Ho una lista interna di (n+1) elementi (che vanno da indice -1 ad indice n), al suo interno ho una lista di n elementi (perchè V è un insieme di n elementi) al cui interno vi è un'altra lista di n elementi)

Ogni elemento della lista più interna è inizializzato ad INFINITO

In pratica da quello che ho capito potrei vedere questa struttura dati costituita da 3 liste una dentro l'altra come una matrice tridimensionale?

Tale matrice nell'algoritmo è la matrice che rappresenta le distanze tra due nodi: u,v al passo k dell'algoritmo (l'algoritmo itera k=n volte prima di restituire il risultato finale con i pesi di tutti gli shortest path tra tutte le coppie di nodi del grafo) ed usa la tecnica della programmazione dinamica per cui il risultato al passo k dipende dalla situazione al passo (k-1). Alla fine dell'algoritmo avrò una matrice d[n][u][v] che mi dice quanto mi costa il cammino minimo tra ogni coppia di nodi u e v.

Se ti diletti anche di algoritmi questo è il codice pseudo Python (perchè in realtà il simbolo di infinito è trattato a livello di pseudo codice e forse anche qualcos'altro) che descrive l'algoritmo per intero commentato:


# Algoritmo che ricevuto un grafo G calcola la lunghezza dei cammini minimi tra tutte le coppie dei suoi nodi
def floydroywarshall(G):

n = len(G) # n contiene il NUMERO DI NODI in G
V = range(n) # V è l'insieme dei noidi del grafo G che sono ordinati da 0 ad n


D = [[[INFINITO for u in V] for v in V] for k in range(-1, n)] # D è la MATRICE DELLE DISTANZE TRA 2 NODI u e v al PASSO k
# P è la MATRICE DEI PREDECESSORI AL PASSO k: In posizione P[k][v][u] si trova il predecessore del nodo u su di uno shortest path che parte dal nodo v al passo k (su un cammino k-vincolato)
P = [[[INFINITO for u in V] for v in V] for k in range(-1, n)]

# Per ogni elemento nella matrice che rappresenta il grafo G. Stò inizializzando la matrice di partenza (con indice k=-1)
for u in V:
for v in V:
if G[u][v] != - INFINITO: # Se esiste un arco pesato che connette direttamente il nodo u con il nodo v
D[-1][u][v] = G[u][v] # Mette in D[-1][u][v] il peso di quell'arco
P[-1][u][v] = u # Il predecessore di v su di uno shortest path 0-vincolato (shortest path senza nodi intermedi) che parte da u è proprio u

# Inizio ad iterare sulla matrice per calcolare i vari cammini k-vincolati (cammini con nodi interni presi da un insieme {0,1,....,k}, quando k == n l'algoritmo termina ed avrò trovato i cammini minimi
for k in V:
for u in V:
for v in V:
# Se mi conviene mantenere il vecchio cammino (k-1) vincolato (con nodi interni presi da {0,1,...,(k-1)})
if D[k-1][u][v] = G[u][v] < D[k-1][u][k] + D[k-1][k][v]:
D[k][u][v] = D[k-1][u][v] # La distanza al passo k-esimo è la stessa rispetto alla distanza al passo (k-1)-esimo
P[k][u][v] = P[k-1][u][v] # Il predecessore di v in uno shortest path k-vincolatto che parte da u è lo stesso dello stesso shortest path (k-1) vincolato

# Se invece mi conviene passare per il k-esimo nodo
else:
# Aggiorno la distanza dello shortest path k-vincolato sommando la somma del costo del cammino (k-1) vincolato che da u arriva a k e del costo del cammino (k-1) vincolato che da
# k arriva a v
D[k][u][v] = D[k-1][u][k] + D[k-1][k][v]
# Il nuovo predecessore di v su uno shortest path k-vincolato che parte da u equivale al predecessore di v su uno shortest path (k-1) vincolato che parte da k
P[k][u][v] = P[k-1][k][v]

return P[n-1]


Ho capito bene cosa stà facendo il professore?

Grazie mille
Andrea

[cdimauro]

Scusa per il ritardo, ma sono stato parecchio incasinato questo mese.

Sì, mi sembra tutto corretto.