De ce contează?
Ai învățat deja să generezi permutările scriind singur backtracking-ul: marchezi un
element, cobori, te întorci, demarchezi. Funcționează, dar e cod pe care îl rescrii
de fiecare dată și în care e ușor să greșești o linie. Imaginează-ți acum că ai un
buton magic: apeși o dată și șirul tău trece la următoarea permutare în ordine
alfabetică; mai apeși, mai trece una; când nu mai există una mai mare, butonul îți
spune „gata". STL-ul C++ are exact acest buton: se numește next_permutation.
Intuiția
Permutările lui {1, 2, 3} au o ordine naturală, ca în dicționar: 123, 132,
213, 231, 312, 321. Aceasta se numește ordine lexicografică —
exact ordinea în care ai citi numerele crescător. Ideea-cheie e că, dată fiind o
permutare, există un mod mecanic de a calcula pe următoarea din această ordine.
STL știe acest mod: next_permutation îți transformă șirul curent în succesorul lui
lexicografic și îți spune dacă a reușit. Tu nu mai construiești nimic poziție cu
poziție — doar ceri „dă-mi următoarea" până nu mai există niciuna.