De ce contează?
Câte aranjamente diferite poți face cu 3 cărți puse în rând? La prima poziție ai 3 variante, la a doua 2 rămase, la a treia 1 — în total 3·2·1 = 6. O permutare e o astfel de aranjare a tuturor elementelor, iar generarea lor e un backtracking clasic.
Ce este o permutare
O permutare a n elemente le folosește pe toate, fiecare exact o dată, într-o
anumită ordine. Numărul de permutări e n! (n factorial): n alegeri la prima poziție,
n−1 la a doua, etc.
Pentru : 123, 132, 213, 231, 312, 321 — 6 = 3! permutări.
Generare prin backtracking cu folosit[]
La fiecare poziție încerci fiecare valoare neutilizată încă. Un vector folosit[] ține
evidența:
#include <iostream>
using namespace std;
int n;
int sol[20];
bool folosit[20];
void genereaza(int pas) {
if (pas == n) { // permutare completa
for (int i = 0; i < n; i++) cout << sol[i] << " ";
cout << "\n";
return;
}
for (int val = 1; val <= n; val++) {
if (!folosit[val]) { // doar valori neutilizate
folosit[val] = true; // alege
sol[pas] = val;
genereaza(pas + 1); // exploreaza
folosit[val] = false; // ANULEAZA (backtrack)
}
}
}
int main() {
n = 3;
genereaza(0); // 123 132 213 231 312 321
return 0;
}Linia folosit[val] = false de după apelul recursiv e backtracking-ul propriu-zis: după
ce ai explorat toate permutările care încep cu val pe poziția pas, îl „eliberezi" ca
să fie disponibil pentru alte ramuri. Fără ea, generezi greșit sau deloc.
Alternativa STL: next_permutation
Dacă vrei permutările în ordine lexicografică, STL le dă direct:
#include <algorithm>
int v[] = {1, 2, 3};
do {
// proceseaza permutarea curenta din v
} while (next_permutation(v, v + 3));next_permutation cere vectorul sortat crescător la început, ca să le parcurgă pe toate.
Complexitate
| Operație | Timp | Spațiu |
|---|---|---|
| generarea tuturor permutărilor | O(n! · n) | O(n) |
n! explodează: 10! ≈ 3,6 milioane, 13! depășește un miliard. Fezabil pentru n ≤ ~10.
Capcane reale la permutări:
- Uiți backtrack-ul
folosit[val] = false: o valoare rămâne marcată și ramurile următoare o ratează → permutări lipsă. - Nu marchezi
folosit: reutilizezi același element → generezi tupluri cu repetiții, nu permutări. next_permutationpe vector nesortat: ratezi permutările dinaintea celei curente. Sortează crescător întâi.- Generezi pentru n mare: n! explodează; verifică limita lui n.
De reținut
- Permutare = toate cele n elemente, fiecare o dată, în orice ordine; n! permutări.
- Backtracking cu
folosit[]: alege valoare neutilizată, explorează, apoi eliberează (backtrack). - Alternativ
next_permutation(vector sortat); fezabil pentru n ≤ ~10.