Backtracking (generarea permutarilor, combinarilor, aranjamentelor)

Backtracking este o tehnică de programare ce explorează sistematic toate soluțiile posibile ale unei probleme, construind soluția pas cu pas și renunțând la drumurile care nu pot duce la o soluție validă (principiul „backtrack” – a da înapoi). Este esențială pentru rezolvarea problemelor de generare a permutărilor, combinațiilor și aranjamentelor.

Generarea permutărilor constă în a produce toate aranjările posibile ale unui set de n elemente (de obicei numere de la 1 la n), fiecare soluție fiind o permutare (șir de n elemente distincte). Algoritmul clasic de backtracking plasează pe fiecare poziție k din stivă (de obicei un vector soluție) un element ales dintre cele rămase, folosind un vector de frecventă pentru a marca ce elemente s-au folosit. Recursivitatea și apelul „back” (de reîncercare) sunt implementate prin metoda: pentru poziția k de la 1 la n, se încearcă toate valorile disponibile; după ce se plasează una, se apelează completarea poziției k+1; la revenire, se demarchează elementul.

Generarea combinațiilor (de n luate câte p) produce submulțimi de p elemente dintr-un set de n, fără a conta ordinea, dar menținând elementele ordonate crescător (de exemplu, pentru a evita duplicările). Backtracking-ul folosește un index de start (de exemplu, „prev” sau „min”) pentru a genera combinații strict crescătoare. Pentru fiecare poziție k, se aleg elemente mai mari decât ultimul ales, începând de la o valoare minimă (1 sau elementul anterior +1).

Astfel se garantează unicitatea combinațiilor.

Generarea aranjamentelor (de n luate câte p) diferă de combinații prin aceea că ordinea elementelor contează. Astfel, pentru fiecare poziție k se poate alege orice element din mulțime (1..n) care nu a fost folosit deja, exact ca la permutări, dar se oprește când s-au selectat p elemente (k de la 1 la p). În acest caz, vectorul de frecventă va marca elementele utilizate, iar la revenire se demarchează.

Diferențe cheie: Permutările au k=n (se folosesc toate elementele), aranjamentele au k=p (p<n), combinațiile au k=p dar elementele sunt în ordine crescătoare (nu se acceptă orice ordine).

Algoritmul backtracking are complexitate exponențială (O(n!), O(C(n,p))), fiind adecvat pentru n sau p mici (de obicei n ≤ 10-12).

Pași generali:

1. Se definește o stivă (vector) pentru soluție.
2. O funcție recursivă backtrack(k) construiește pasul k.
3. La primul apel (k=1) se încearcă toate valorile posibile conform regulii problemei.
4. Se validează condițiile (de exemplu, elementul să nu mai fi fost folosit).
5. Se plasează valoarea, se marchează, se continuă cu k+1 (sau se afișează dacă s-a atins dimensiunea finală).
6. La revenire, se demarchează.

Această tehnică este fundamentală pentru Bacalaureat și pentru înțelegerea programării recursive.

Exemple

• Exemplul 1: Generarea permutărilor pentru n=3
• Problemă: Să se afișeze toate permutările mulțimii {1,2,3}.
• Rezolvare: Se utilizează un vector stack[4] (de la 1 la 3) și un vector frec[4] (inițial 0). Funcția backtrack(k) încearcă valori de la 1 la 3. Dacă frec[i]==0, se plasează, se marchează, se apelează backtrack(k+1). Când k=4, se afișează stack[1..3]. Se demarchează la revenire.
• Soluțiile generate: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1) – 3! = 6 permutări.
• Observație: Ordinea de generare este cea lexicografică datorită parcurgerii crescătoare a valorilor.

Exemplul 2: Generarea combinațiilor de n=4 luate câte p=2

• Problemă: Submulțimile de 2 elemente ale mulțimii {1,2,3,4}.
• Rezolvare: Se folosește un vector sol[p+1] (p=2). Funcția backtrack(k, start) încearcă valori i de la start la n. Se plasează i în sol[k] și se apelează backtrack(k+1, i+1). Când k > p, se afișează combinația.
• Soluțiile: (1,2), (1,3), (1,4), (2,3), (2,4), (3,4) – C(4,2)=6 combinații.
• Observație: Parametrul start garantează ordinea crescătoare și evită duplicarea (de ex., (1,2) nu apare ca (2,1)).

Exemplul 3: Generarea aranjamentelor de n=4 luate câte p=2

• Problemă: Toate aranjamentele (perechi ordonate) de 2 elemente din mulțimea {1,2,3,4}.
• Rezolvare: Similar cu permutările, dar lungimea soluției este p=2. Backtrack(k) încearcă valori i de la 1 la n, cu condiția ca frec[i]==0. Se plasează, se marchează, se apelează backtrack(k+1). Când k>p (k=3) se afișează. Se demarchează la revenire.
• Soluțiile: (1,2),(1,3),(1,4),(2,1),(2,3),(2,4),(3,1),(3,2),(3,4),(4,1),(4,2),(4,3) – A(4,2)=12 aranjamente.
• Observație: Spre deosebire de combinații, (1,2) și (2,1) sunt diferite.

Concepte cheie: Backtracking - renunțare la soluții parțiale care nu pot fi completate, Permutări - n elemente, toate ordonările posibile, n! soluții, Combinații - submulțimi de p elemente din n, ordinea nu contează, C(n,p) soluții, Aranjamente - n luate câte p, ordinea contează, fără repetiții, A(n,p) = n!/(n-p)! soluții, Stivă (vector soluție) și vector de frecvență, Parametru de start pentru combinații (evitare duplicare), Recursivitate și demarcare (backtrack) la revenire, Complexitate exponențială – aplicabil pentru n sau p mici