Tehnici de generare a permutarilor si submultimilor (Bac)

Generarea permutarilor și a submultimilor reprezintă două dintre cele mai importante tehnici de backtracking studiate în liceu, esențiale pentru rezolvarea problemelor de combinatorică la Bacalaureat. O permutare a unei mulțimi de n elemente este o aranjare ordonată a acestora, fără repetiții. Numărul de permutări este n! (factorial).

Algoritmul clasic de generare a permutărilor folosește o stare (stiva) în care se construiește pas cu pas soluția, verificând la fiecare pas dacă elementul curent a fost deja folosit (vector de frecvență). Funcția de validare returnează true dacă elementul nu a fost încă ales. Se parcurge recursiv sau iterativ, iar la atingerea unei lungimi egale cu n, se tipărește soluția.

Pentru submultimi (combinații fără repetiție), generarea se face similar, dar se impune ca elementele să fie în ordine strict crescătoare pentru a evita rearanjări. Practic, se generează submulțimi de k elemente dintr-o mulțime de n, iar numărul acestora este dat de combinări de n luate câte k (C(n,k)). Algoritmul folosește un vector soluție de lungime k, iar la fiecare pas se alege un element mai mare decât ultimul ales, pentru a menține ordinea.

O variantă avansată este generarea submultimilor cu ajutorul măștilor de biți (bitmask), utilă pentru submultimile tuturor mulțimilor (puterea mulțimii). În acest caz, un număr între 0 și 2^n - 1 reprezintă o submulțime: bitul i indică prezența elementului i. Această tehnică este eficientă pentru n mic (de obicei n ≤ 20) și este frecvent întâlnită în probleme de tip 'subsets' sau 'combinatorics'.

La Bac, se cere adesea implementarea recursivă a permutărilor și a combinărilor, precum și înțelegerea conceptului de backtracking. Este important să rețineți că pentru permutări se folosește un vector de frecvență (folosit[i] = 1 dacă elementul i este deja în soluție), iar pentru combinări se folosește o variabilă 'ultim' care reține ultimul element ales, pentru a nu repeta combinații identice. Tehnica de generare a submultimilor prin backtracking este similară, dar nu se mai verifică frecvența, ci doar ordinea crescătoare.

În practică, multe probleme de Bac (de exemplu, generarea anagramelor sau a echipelor) se bazează pe aceste tehnici.

Exemple

• Exemplul 1: Generarea permutărilor pentru n=3. Algoritmul pornește cu stiva goală. La pasul 1, alege 1, marcat ca folosit. La pasul 2, alege 2, apoi 3. Soluție: 1 2 3. Apoi revine la pasul 2 și alege 3, apoi 2 -> 1 3 2. Revine la pasul 1, alege 2, apoi continuă cu 1 și 3 -> 2 1 3, 2 3 1, etc. Total 6 permutări.
• Exemplul 2: Generarea combinărilor de 3 luate câte 2. Mulțime: {1,2,3}. Algoritmul alege primul element 1, apoi al doilea element mai mare decât 1: 2 -> soluția [1,2]. Apoi [1,3], [2,3]. Nu se generează [2,1] deoarece ar fi aceeași combinație. Numărul de soluții: C(3,2)=3.
• Exemplul 3: Generarea submultimilor (puterea mulțimii) prin bitmask pentru n=3. Numerele de la 0 la 7: 0 (000) -> mulțimea vidă; 1 (001) -> {1}; 2 (010) -> {2}; 3 (011) -> {1,2}; 4 (100) -> {3}; 5 (101) -> {1,3}; 6 (110) -> {2,3}; 7 (111) -> {1,2,3}. Total 2^3=8 submulțimi.

Concepte cheie: Backtracking, Permutări (n!), Combinări (C(n,k)), Vector de frecvență, Ordonare crescătoare pentru evitarea duplicării, Bitmask pentru submulțimi (2^n)