Probleme Rezolvate

Se citesc de la tastatură numerele naturale n, m1, m2, m3, ..., mn unde n reprezintă un număr de mulțimi, iar mj numărul de elemente al mulțimii Ai = (1, 2, 3, ..., mi). Să se genereze recursiv produsul cartezian al celor n mulțimi: A1 x A2 x ... x An.
Pentru a genera produsul cartezian al n mulțimi, putem folosi un algoritm recursiv.
Idee de bază:
Pentru a implementa acest algoritm, vom crea o structură de date List care va conține toate perechile de elemente din produsul cartezian. Vom parcurge mulțimile în ordine recursivă, începând cu prima mulțime A1, și vom adăuga toate perechile de elemente în List . În apelul recursiv, vom trece la următoarea mulțime și vom genera toate perechile posibile cu elementele din List-ul anterior. Vom continua astfel până când am parcurs toate mulțimile.

# include < iostream >
using namespace std ;
struct Pair {
int first ;
int second ;
};
struct List {
Pair pair ;
List * next ;
};
List * addPair ( List * list , int a, int b) {
List * node = new List ;
node -> pair.first = a;
node -> pair.second = b;
node -> next = list ;
return node ;
}
void printList ( List * list ) {
cout << "{" ;
while ( list ) {
cout << "(" << list -> pair.first << ", " << list -> pair.second << ")" ;
list = list -> next ;
if ( list ) {
cout << ", " ;
}
}
cout << "}" << endl ;
}
void generateCartesianProduct ( List * list , int n, int * m) {
if (n == 0 ) {
printList ( list );
return ;
}
for ( int i = 1 ; i <= m[n]; i++) {
List * node = list ;
while ( node ) {
generateCartesianProduct ( addPair ( list , i, node -> pair.first ), n - 1 , m);
node = node -> next ;
}
list = addPair ( list , i, 0 );
}
}
int main () {
int n, m[ 100 ];
cin >> n;
for ( int i = 1 ; i <= n; i++) {
cin >> m[i];
}
generateCartesianProduct ( NULL , n, m);
return 0 ;
}

Explicații: