De ce contează?
Ai trei prieteni — Ana, Bogdan, Carla — și o singură bancă cu trei locuri. În câte moduri îi poți așeza? Începi prin a alege cine stă pe primul loc, apoi pe al doilea dintre cei rămași, apoi ultimul se așază singur. Dacă vrei să le notezi pe toate fără să uiți niciuna și fără să repeți, ai nevoie de o regulă: încerci o variantă, mergi până la capăt, apoi te întorci și încerci alta. Exact asta face un calculator când generează toate permutările.
Intuiția
O permutare este o ordonare a elementelor — pentru mulțimea {1, 2, 3} există 6:
123, 132, 213, 231, 312, 321. Ideea de bază e să construiești permutarea
poziție cu poziție: pe prima poziție pui un element, pe a doua un alt element
nefolosit, pe a treia ultimul rămas. Când ai umplut toate pozițiile, ai o permutare
completă. Apoi te întorci la ultima alegere, o anulezi și încerci următoarea
variantă — așa explorezi pe rând toate combinațiile, fără să sari peste niciuna.