Candale Silviu (silviu) Problema:
Se dă un număr natural
n. Să se genereze toate submulțimile mulțimii{1,2,3,...,n}.
Soluție:
Pentru rezolvare folosim metoda backtracking. Acest articol prezintă două metode de rezolvare.
Metoda 1
În vectorul soluție x[] vom memora pe rând câte o submulțime. Deoarece submulțimile au număr variabil de elemente, și vectorul soluție va avea un număr variabil de elemente.
- semnificaţia vectorului soluție:
x[]reprezintă la un moment dat o submulțime - condiții externe:
x[k]în{1,2,..,n},kîntre1șin; - condiții interne:
x[k]>x[i],iîntre1șik-1. Deoarece condițiile interne se aplică pentru toate elementele vectorului soluție, este suficient cax[k]>x[k-1], pentruk>1; - condiții de existența a soluției: fiecare variantă a vectorului soluție corespunde cu o submulțime. Orice valoare validă plasată în vectorul soluție conduce la o soluție.
void afis(int k){
for(int i=1 ; i<=k ; ++i)
cout << x[i] << " ";
cout << endl;
}
bool valid(int k){
if(k == 1)
return true;
if(x[k] > x[k-1])
return true;
return false;
}
void back(int k){
for(int i=1;i<=n;++i)
{
x[k]=i;
if(valid(k))
{
afis(k);
back(k+1);
}
}
}
Constatăm că putem rafina condițiile externe; deoarece x[k]>x[k-1], condițiile devin:
- Condiții externe:
x[k]în{x[k-1]+1, ... , n},kîntre1șin. Pentru a uniformiza algoritmul, considerăm de la început căx[0] = 0; - Condiții interne: nu mai avem condiții interne; funcția
valid()nu mai este necesară; - Condiții de existența a soluției rămân aceleași.
void back(int k){
for(int i=x[k-1]+1;i<=n;++i)
{
x[k]=i;
afis(k);
back(k+1);
}
}
Să observăm că submulțimea vidă nu se regăsește printre soluțiile generate cu acest algoritm. Dacă este cazul, afișarea ei se poate face în afara algoritmului de generare.
Metoda 2
Această metodă se bazează pe observația că pentru fiecare submulțime a mulțimii date, {1,2,...,n} îi corespunde un șir de n biți, notat x[], astfel:
- dacă bitul
x[k] = 0, elementulknu aparține submulțimii curente; - dacă bitul
x[k] = 1, elementulkaparține submulțimii curente.
Reamintim că o mulțime cu n elemente are 2 n submulțimi.
Exemplificăm cu mulțimea {1,2,3,4}.
0 |
0000 |
{} |
8 |
1000 |
{1} |
1 |
0001 |
{4} |
9 |
1001 |
{1,4} |
2 |
0010 |
{3} |
10 |
1010 |
{1,3} |
3 |
0011 |
{3,4} |
11 |
1011 |
{1,3,4} |
4 |
0100 |
{2} |
12 |
1100 |
{1,2} |
5 |
0101 |
{2,4} |
13 |
1101 |
{1,2,4} |
6 |
0110 |
{2,3} |
14 |
1110 |
{1,2,3} |
7 |
0111 |
{2,3,4} |
15 |
1111 |
{1,2,3,4} |
Putem să generăm toate șirurile de n biți, iar pentru fiecare șir să construim submulțimea corespunzătoare. Generarea șirurilor se poate face în mai multe moduri:
- parcurgem numerele de la
0la2n-1și transformăm fiecare număr în baza2; obținem astfel pentru fiecare număr un șir de biți care va fi transformat în submulțime; - generăm direct șirul de biți cerut cu metoda backtracking.
Vom detalia mai jos rezolvarea cu backtracking:
- semnificaţia vectorului soluție:
x[]conține la un moment dat un șir de biți care va corespunde unei submulțimi - condiții externe:
x[k] = 0sau1; - condiții interne nu există. Orice configurație parțială a vectorului
x[]va conduce la o soluție validă - condiții de existență a soluției:
k == n.
void afis(int k){
for(int i=1 ; i <= k ; ++i)
if(x[i] == 1)
cout << i << " ";
cout << endl;
}
void back(int k){
for(int i = 0; i <= 1 ; ++i)
{
x[k]=i;
if(k == n)
afis(k);
else
back(k+1);
}
}
Probleme
SubmDiv Submultimi Siruri