[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.

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 ).

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.

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.