Metoda backtracking. Generarea permutărilor. Generarea partiţiilor unei mulţimi

Apărut la 12 octormbrie 2018 în C / C++   |   autor: Dan Pracsiu 0 comentarii

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 A₁, A₂, ..., A_p 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 A_j. 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 ;
}

Număr de accesări: 35905

Dan Pracsiu deţinător www.dponline.ro
Profesor, Liceul Teoretic "Emil Racoviță" Vaslui
Membru în Comisia Naţională a Olimpiadelor de Informatică
Pasiuni: istoria, călătoriile, fotografia, muzica clasică