Generarea mulţimilor

                                        A.Generarea produsului cartezian


             Se consideră n mulţimi A1, A2, ... , An de forma {1,2..,an}. Să se genereze produsul  cartezian al acestor mulţimi.
Am considerat mulţimile de forma {1,2..,an} pentru a simplifica problema, în special la partea de citire si afişare, algoritmul de generare rămânând nemodificat.
             Identificăm următoarele particularităţi şi condiţii:

             Fiecare element Xk din vectorul soluţie aparţine unei mulţimi {1,2..,ak}. Aici este o diferenţă faţă de algoritmii anteriori în care fiecare element din soluţie era luat din aceeaşi mulţime şi trebuie să avem grijă la acest fapt când scriem programul.
             Nu există condiţii între elementele vectorului soluţie.
             Obţinem soluţia când s-au generat n valori.


                                       B.Generarea submulţimilor unei mulţimi


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


                                      C. Generarea partiţiilor unei mulţimi


             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.