Partitiile unei multimi

Generăm partiţiilor unei mulţimi presupune împărţirea mulţimii în mulţimi nevide şi disjuncte care reunite să dea întreaga mulţime. Putem, ca şi în cazurile anterioare, să considerăm mulţimea {1,2,…,n}. Construim un vector soluţie în care pentru fiecare element vom trece submulţimea în care îl vom include. Această submulţime mai este numită şi clasă.

Algoritmul generează pe rând toate modalităţile de a împărţi elementele mulţimii {1,2,…,n} folosind mai întâi o singură clasă, apoi două, ş.a.m.d. până la n clase.

NUNT: Fie n numar natural nenul. Scrieti un program de generare a tuturor partitiilor multimii {1, 2, 3,..., n}.

EXEMPLU: Pentru n=3 programul va genera

{1} {2} {3}

{1} {2,3}

{2} {1,3}

{3} {1,2}

{1,2,3}

SOLUTIE: Prin partitie se intelege o descompunere a multimii initiale intr-o reuniune de multimi nevide si disjuncte. Pentru o multime cu n elemente vor exista maxim n multimi in cadrul unei partitii.

• Solutia x[1]......x[n]. Fiecare multime din cadrul partitiei va fi codificata cu numere de la 1 la n. Elementul x[i] va avea ca valoare numarul asociat multimii din care face parte.

Solutia Codificare

{1,2,3} 1 1 1

{1,2} {3} 1 1 2

{1,3} {2} 1 2 1

{1} {2,3} 1 2 2

{1} {2} {3} 1 2 3

• x[k] poate avea ca valoare orice valoare din intervalul [1,k]. Dar cele mai mari doua elemente din cadrul codificarii unei partitii nu pot sa difere decat printr-o unitate.

• Valid - nu este necesar

PROGRAM C++:

#include <iostream>

using namespace std;

char sp3[]=" ";

int x3[20], n3, nrsol3=0, max[20], maxim;

int DeterminareMaxim(int k)

{ int maxim=0,i;

for(i=1;i<=k;i++)

if (x3[i]>maxim) maxim=x3[i];

return maxim;

}

void Afisare3()

{ int i,j;

cout<<sp3;

maxim=DeterminareMaxim(n3);

for(j=1;j<=maxim;j++)

{ cout<<"{";

for(i=1;i<=n3;i++)

if (x3[i]==j) cout<<i<<" ";

cout<<"} ";

}

cout<<endl;

nrsol3++;

}

void BackRec3(int k)

{ int i;

for(i=1;i<=DeterminareMaxim(k-1)+1;i++)

{ x3[k]=i;

if (k==n3) Afisare3();

else BackRec3(k+1);

}

}

int main()

{ cout<<endl<<endl<<sp3<<"Partiile multimii {1,2,3.....,n}"<<endl;

cout<<endl<<sp3<<" Dati valoarea lui n: "; cin>>n3;

cout<<endl;

BackRec3(1);

cout<<endl<<sp3<<"Numar solutii: "<<nrsol3;

return 0;

}