Transpunerea matricei pe loc nu schimbă nimic: fiecare pereche e interschimbată de două ori
Bucla j parcurge toată matricea, deci fiecare pereche (i, j) e interschimbată o dată la (i, j) și încă o dată la (j, i), iar matricea revine la forma inițială. Pornește a doua buclă de la i + 1: for j in range(i + 1, n).
Explicat de Tudor Andrei Dumitrescu, Senior Software Developer, fondatorul Academiei ProgramatorilorActualizat la
Ce înseamnă
Transpunerea pe loc a unei matrice pătratice înseamnă să interschimbi m[i][j] cu m[j][i] pentru fiecare pereche de poziții simetrice față de diagonala principală. Fiecare pereche trebuie interschimbată o singură dată.
Dacă ambele bucle merg de la 0 la n, perechea e vizitată de două ori: o dată când i < j și încă o dată când i > j. A doua interschimbare o anulează pe prima, iar la final matricea arată exact ca la început. Diagonala (i == j) se interschimbă cu ea însăși, deci nu contează.
Aceeași greșeală strică și rotirea cu 90 de grade (transpunere urmată de inversarea fiecărui rând): rotirea iese o simplă oglindire. Parcurge doar triunghiul de deasupra diagonalei: for j in range(i + 1, n).
De ce apare: cauzele frecvente
1Ambele bucle parcurg toată matricea
for i in range(n):
for j in range(n):
m[i][j], m[j][i] = m[j][i], m[i][j]for i in range(n):
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]Cu j de la i + 1, fiecare pereche simetrică e atinsă o singură dată, din triunghiul de deasupra diagonalei.
2Rotirea cu 90 de grade folosește aceeași transpunere
transpune(m) # cu bucla greșită
for rand in m:
rand.reverse()for i in range(n):
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
for rand in m:
rand.reverse()Rotirea în sensul acelor de ceasornic e transpunere plus inversarea rândurilor. Dacă transpunerea nu face nimic, rămâne doar oglindirea.
3Varianta fără modificare pe loc
for i in range(n):
for j in range(n):
m[i][j], m[j][i] = m[j][i], m[i][j]t = [list(rand) for rand in zip(*m)]Când nu ți se cere explicit transpunerea pe loc, zip(*m) construiește matricea transpusă direct, fără risc de dublă interschimbare.
Repară eroarea, direct în pagină
Funcția transpune(m) trebuie să transpună pe loc o matrice pătratică. Testul cu assert pică: matricea rămâne neschimbată. Repar-o ca să afișeze [[1, 3], [2, 4]] pentru [[1, 2], [3, 4]].
def transpune(m):
n = len(m)
for i in range(n):
for j in range(n):
m[i][j], m[j][i] = m[j][i], m[i][j]
return m
m = transpune([[1, 2], [3, 4]])
assert m == [[1, 3], [2, 4]], f'matrice netranspusa: {m}'
print(m)[[1, 3], [2, 4]]
Indiciu
Fiecare pereche simetrică trebuie interschimbată o singură dată: a doua buclă pornește după diagonală.
Reparația
def transpune(m):
n = len(m)
for i in range(n):
for j in range(i + 1, n):
m[i][j], m[j][i] = m[j][i], m[i][j]
return m
m = transpune([[1, 2], [3, 4]])
assert m == [[1, 3], [2, 4]], f'matrice netranspusa: {m}'
print(m)De ce merge
Cu ambele bucle de la 0 la n, perechea (0, 1) era interschimbată o dată când i = 0, j = 1 și încă o dată când i = 1, j = 0, iar valorile 2 și 3 reveneau la locul lor. Cu range(i + 1, n), bucla parcurge doar pozițiile de deasupra diagonalei, deci fiecare pereche e interschimbată exact o dată, iar 2 și 3 rămân schimbate.
Cum o eviți pe viitor
La orice operație pe perechi simetrice (transpunere, comparații i cu j, muchii neorientate dintr-o matrice de adiacență), întreabă-te dacă perechea trebuie tratată o dată sau de două ori. Pentru „o dată”, folosește range(i + 1, n). Testează pe o matrice 2×2 cu valori diferite ([[1, 2], [3, 4]]): rezultatul așteptat se verifică imediat cu ochiul.
Întrebări frecvente
Merge la fel pentru o matrice dreptunghiulară?
Nu. Transpusa unei matrice n×m are m rânduri și n coloane, deci nu se poate face pe loc în aceeași listă de liste. Construiește una nouă cu [list(r) for r in zip(*m)].
De ce nu dă nicio eroare?
Toți indicii sunt valizi, iar fiecare interschimbare e corectă luată separat. Problema e doar că a doua o anulează pe prima.
Erori înrudite
IndexError: list index out of range la parcurgerea unei matrice Ai inversat numărul de rânduri cu numărul de coloane (sau i cu j) la o matrice care nu e pătrată. len(grila) e numărul de rânduri, len(grila[0]) e numărul de coloane, iar accesul se face mereu grila[rand][coloana]. [[0] * m] * n: modifici o celulă și se schimbă toată coloana [[0] * m] * n nu creează n rânduri, ci n referințe la același rând, așa că dp[0][1] = 5 apare în toate rândurile. Creează fiecare rând separat: [[0] * m for _ in range(n)]. grila.copy() (sau grila[:]) pe o matrice: modifici copia și se schimbă și originalul copy() și [:] fac o copie superficială: lista nouă conține aceleași rânduri ca originalul. Modificarea unei celule apare în ambele. Pentru o matrice copiază fiecare rând: [rand[:] for rand in grila], sau folosește copy.deepcopy(grila). Învață Algoritmi și structuri de date de la zero, cu exerciții la fiecare lecție
Curs Algoritmi pentru interviuri: lecții scurte, fiecare cu un exercițiu verificat automat, direct în browser. Primele 2 lecții sunt gratuite.
