De ce contează?
Ai 3 alergători la o cursă și vrei să afișezi clasamentul: cine ia aurul și cine ia argintul. „Ana, apoi Bogdan" e cu totul altceva decât „Bogdan, apoi Ana" — deși e vorba de aceiași doi oameni. Aici ordinea contează: nu te interesează doar care doi urcă pe podium, ci și pe ce loc. Câte clasamente de două locuri poți forma din 3 alergători? Asta înseamnă aranjamente.
Intuiția
Aranjamentele A(n, k) numără în câte feluri poți alege și ordona k elemente
dintr-o mulțime de n. E aproape ca la permutări — pui elemente unul după altul și
nu repeți ce ai folosit deja — doar că te oprești după k poziții, nu după toate
n. Pentru că ordinea contează, 12 și 21 sunt două soluții diferite, exact ca
două clasamente diferite.
Generarea folosește același tipar ca permutările: încerci pe fiecare poziție orice
element încă nefolosit, cobori recursiv, apoi te întorci (backtracking) și
încerci alt element. Diferența e o singură linie: oprirea se face la adâncimea k.