Metoda backtracking. Generarea permutărilor. Generarea partițiilor unei mulțimi
Voi considera în acest articol faptul că cititorii cunosc noţiunile teoretice legate de metoda backtracking. Voi prefera implementarea utilizând varianta recursivă a problemelor menţionate.
Problema 1. Se citeşte un număr natural n. Se cere să se afişeze toate permutările mulţimii {1, 2, ..., n}.
Soluţia, ca orice problemă de backtracking liniar, este o stivă. Lungimea stivei este n, iar pe orice nivel al stivei vom depune elementele distincte ale mulţimii {1,2,...,n}. Pentru a evita memorarea într-o soluţie a aceleiaşi valori, utilizăm vectorul viz de lungime n, în care viz[i] = 0 dacă i nu a fost pus încă pe stivă şi viz[i]=1 dacă i este deja pe stivă. Aceasta înseamnă că dacă de exemplu pe stivă am memorat deja valorile 3, 6, 2, atunci în vectorul viz avem viz[3] = 1, viz[6] = 1, viz[2] = 1, restul componentelor fiind 0. Pentru nivelul 4 al stivei vom putea depune acum orice valoare i în care viz[i]=0.
#include<iostream> using namespace std; int a[20], n, viz[20]; void PrintSol() { int i; for (i = 1; i <= n; i++) cout << a[i] << " "; cout << "\n"; } void Back(int top) { int i; if (top == n + 1) PrintSol(); else for (i = 1; i <=n; i++) if (!viz[i]) { viz[i] = 1; a[top] = i; Back(top + 1); viz[i] = 0; } } int main() { cout << "n = "; cin >> n; Back(1); return 0 ; }
Problema 2. Se citeşte un număr natural n. Să se genereze partiţiile mulţimii {1,2,...,n}. O partiţie a unei mulţimi A se defineşte ca fiind un set de mulţimi A1, A2, ..., Ap nevide, distincte două câte două, iar reuniunea celor p mulţimi este A. De exemplu, mulţimea {1,2,3,4,5} are ca partiţie setul {1,3,4}{2,5} sau setul {1,4} {2} {3,5}.
Utilizăm în rezolvare o stivă de lungime n, în care st[i] = j are semnificaţia că elementul i aparţine mulţimii Aj. De exemplu, pentru mulţimea {1,2,3,4,5}, partiţia {1,3,4}{2,5} se memorează astfel: st = (1,2,1,1,2). Ideea va fi în continuare ca la fiecare nivel top al stivei să trebuiască pusă o valoare cuprinsă între 1 şi 1 + maxim(st[i], 1 <= i < top}. De ce această restricţie? Pentru că st = (1,2,1,1,2) este aceeaşi cu st = (1,3,1,1,3). Este memorată aceeaşi partiţie. Îentru aceasta, vom utiliza un vector suplimentar maxim, în care maxim[i] va memora valoarea maximă din subvectorul st[1.. i-1].
#include<iostream>
using namespace std;
int a[20], n, viz[20], maxim[20];
void PrintSol()
{
int i, j;
for (i = 1; i <= maxim[n]; i++)
{
cout << "{ ";
for (j = 1; j <= n; j++)
if (a[j] == i)
cout << j << " ";
cout << "}";
}
cout <<"\n";
}
void Back(int top)
{
int i;
if (top == n + 1) PrintSol();
else for (i = 1; i <= maxim[top - 1] + 1; i++)
{
a[top] = i;
maxim[top] = max(maxim[top-1],i);
Back(top + 1);
}
}
int main()
{
cout << "n = ";
cin >> n;
Back(1);
return 0 ;
}