Produs cartezian — toate combinațiile dintre mulțimi

De ce contează?

La un fast-food alegi un fel principal ȘI un desert. Trei principale, două deserturi — câte meniuri diferite poți compune? Le numeri pe toate: fiecare principal merge cu fiecare desert. Mulțimea acestor perechi este produsul cartezian.

Ce este produsul cartezian

Produsul cartezian a două mulțimi A și B este mulțimea tuturor perechilor (a, b) cu a din A și b din B. Dacă A are m elemente și B are p, produsul are m · p perechi. Pentru k mulțimi, înmulțești toate mărimile.

Observația-cheie

Deosebirea de submulțimi: aici alegi exact un element din fiecare mulțime și le combini. La submulțimi lucrai cu o singură mulțime și decideai prezent/absent.

Algoritmul pas cu pas

Pentru A = {1, 2, 3} și B = {x, y}, parcurgem toate perechile cu două bucle imbricate:

perechi

3 × 2 = 6 perechi. Bucla exterioară fixează elementul din A, cea interioară parcurge B.

Implementare C++ (două mulțimi)

#include <iostream>
using namespace std;

int main() {
    int A[] = {1, 2, 3};
    char B[] = {'x', 'y'};
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 2; j++) {
            cout << "(" << A[i] << "," << B[j] << ") ";
        }
    }
    // (1,x) (1,y) (2,x) (2,y) (3,x) (3,y)
    return 0;
}

Când numărul de mulțimi nu e fix

Dacă ai k mulțimi, dar k se află abia la rulare, nu poți scrie k bucle. Folosești recursivitate: fiecare nivel alege elementul de pe o poziție.

#include <iostream>
using namespace std;

int n[] = {3, 2, 2};   // marimile celor k=3 multimi
int k = 3;
int sol[20];

void produs(int poz) {
    if (poz == k) {                 // am ales cate un element din fiecare
        for (int i = 0; i < k; i++) cout << sol[i];
        cout << " ";
        return;
    }
    for (int val = 0; val < n[poz]; val++) {
        sol[poz] = val;             // alege un element din multimea curenta
        produs(poz + 1);
    }
}

int main() {
    produs(0);                      // 3*2*2 = 12 combinatii
    return 0;
}

Complexitate

Caz	Timp	Spațiu
`k` mulțimi de mărimi `n₁..n_k`	O(n₁ · n₂ · ... · n_k · k)	O(k)

Numărul de rezultate este produsul mărimilor — crește foarte repede.

Greșeli frecvente

Greșeli reale:

Aduni în loc să înmulțești. Numărul de combinații e m · p, nu m + p.
Hard-codezi k bucle când k e variabil → cod care nu se compilează pentru alt k. Folosește recursivitatea.
Uiți cazul de bază (poz == k) în varianta recursivă → recursivitate infinită.
Refolosești sol fără să-l rescrii complet pe fiecare nivel — fiecare apel trebuie să seteze sol[poz] înainte de a coborî.

Recapitulare

Produsul cartezian = toate combinațiile cu câte un element din fiecare mulțime.
Numărul de combinații e produsul mărimilor (înmulțire, nu adunare).
Pentru k fix folosești bucle imbricate; pentru k variabil, recursivitate (un nivel per mulțime).