Generarea submulţimilor unei mulţimi A cu n elemente se poate face cu ajutorul algoritmului de generare a combinărilor, apelându-l repetat cu valorile 1, 2, …, n pentru a genera submulţimile cu un element, apoi cele cu două elemente, apoi cu 3 elemente etc.
Această modalitate de rezolvare este şi mai complicată şi mai puţin eficientă decât următoarea, care se bazează pe generarea produsului cartezian {0,1}n. Această a doua metodă este eficientă deoarece generează 2n soluţii, adică exact atâtea câte submulţimi are o mulţime cu n elemente.
Aşadar, generăm toate combinaţiile de lungime n cu valorile 0 şi 1. Pentru fiecare combinaţie parcurgem soluţia X şi afişăm elementele din mulţimea A cărora le corespund valori 1 în X. Astfel, pentru combinaţia 001011 vom afişa elementele de pe poziţiile 3, 5 şi 6 din mulţimea iniţială.
ENUNT: Fie n numar natural nenul. Scrieti un program de generare a tuturor submultimilor multimii {1, 2, 3,..., n}.
EXEMPLU: Pentru n=3 programul va genera
{} {1} {2} {3} {1,2} {1,3} {2,3} {1,2,3}
SOLUTIE:
Solutia x[1]......x[n] - x[i] poate fi 0 (i nu apartine submultii) sau 1 (i apartine submultimii)
Solutia Codificare
{} 0 0 0
{3} 0 0 1
{2} 0 1 0
{2,3} 0 1 1
{1} 1 0 0
{1,3} 1 0 1
{1,2} 1 1 0
{1,2,3} 1 1 1
x[k] poate fi 0 sau 1
Valid - nu este necesar
PROGRAM C++:
#include <iostream>
using namespace std;
char sp2[]=" ";
int x2[20], n2, nrsol2=0;
void Afisare2()
{ int i;
cout<<sp2<<"{ ";
for(i=1;i<=n2;i++)
if (x2[i]==1) cout<<i<<" ";
cout<<char(8)<<"}"<<endl;
nrsol2++;
}
void BackRec2(int k)
{ int i;
for(i=0;i<=1;i++)
{ x2[k]=i;
if (k==n2) Afisare2();
else BackRec2(k+1);
}
}
int main()
{ cout<<endl<<endl<<sp2<<"Submultimile multimii {1,2,3.....,n}"<<endl;
cout<<endl<<sp2<<" Dati valoarea lui n: "; cin>>n2;
cout<<endl;
BackRec2(1);
cout<<endl<<sp2<<"Numar solutii: "<<nrsol2;
return 0;
}