Probleme Rezolvate

Să se genereze recursiv partițiile mulțimii X= (1, 2, 3, ..., n), cu n apartine N. O partiție a mulțimii X se formează prin descompunerea mulțimii într-o reuniune de mulțimi disjuncte: X = X1 reunit X2 reunit ... reunit Xi , unde i apartine N şi i<= n.
Pentru a genera recursiv toate partițiile mulțimii X=(1,2,3,...,n), putem utiliza următorul algoritm:

# include < iostream >
void genereazaPartitii ( int n, int k) {
static int parti [ 100 ];
if (n == 0 ) {
// Am generat o partiție nouă, o afișăm
for ( int i = 0 ; i < k; i++) {
std :: cout << parti [i] << " " ;
}
std :: cout << std :: endl ;
} else {
// Generăm partițiile pentru n-1
genereazaPartitii (n -1 , k);
// Adăugăm elementul n la fiecare submulțime existentă
for ( int i = 0 ; i < k; i++) {
int tmp = parti [i];
parti [i] = n;
parti [k++] = tmp ;
genereazaPartitii (n -1 , k);
k--;
parti [i] = tmp ;
}
// Adăugăm elementul n ca o submulțime separată
parti [k++] = n;
genereazaPartitii (n -1 , k);
k--;
}
}
int main () {
int n;
std :: cout << " Introduceti valoarea lui n: " ;
std ::cin >> n;
std :: cout << " Partitiile lui " << n << " sunt:\n" ;
genereazaPartitii (n, 0 );
return 0 ;
}

La fiecare apel al funcției genereazaPartitii , verificăm dacă am ajuns la final (n=0) și am generat o nouă partiție. Dacă nu, generăm partițiile pentru n-1 și adăugăm elementul n la fiecare submulțime existentă, dar și ca o submulțime separată. Utilizăm un vector static pentru a stoca elementele partițiilor pentru a evita alocarea repetată de memorie.
Exemplu de output pentru n=3:
Partitiile lui 3 sunt:
1 2 3
1 3 2
1 2
1 3
2 3
1
2
3