Generarea partitiilor unei multimi

Generarea partitiilor unei multimi

ENUNT  : 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.


   I. 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


  II. 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.

 III. Valid - nu este necesar

 Implementare
#include<iostream>
using namespace std;

char sp[]="   ";

int x[20], n, nrsol=0, max[20], maxim;

int DeterminareMaxim(int k)
{int maxim=0,i;
   for(i=1;i<=k;i++)
     if (x[i]>maxim) maxim=x[i];
 return maxim;
}


void Afisare()
{int i,j;
 cout<<sp;
 maxim=DeterminareMaxim(n);
 for(j=1;j<=maxim;j++)
   {cout<<"{";
    for(i=1;i<=n;i++)
    if (x[i]==j) cout<<i<<" ";
       cout<<"}  ";
   }
 cout<<endl;
 nrsol++;
 if (nrsol%22==0) cin.get();
}

void BackRec(int k)
{int i;
   for(i=1;i<=DeterminareMaxim(k-1)+1;i++)
      { x[k]=i;
       if (k==n) Afisare();
       else BackRec(k+1);
      }
}


int main()
{cout<<endl<<endl<<sp<<"Partiile multimii {1,2,3.....,n}"<<endl;
 cout<<endl<<sp<<" Dati valoarea lui n: "; cin>>n;
 cout<<endl;
 BackRec(1);
 cout<<endl<<sp<<"Numar solutii: "<<nrsol;
 return 0;
}