Generarea submultimilor

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;

}