De ce contează?
La un local cu 3 feluri de bază și 2 garnituri, câte meniuri diferite poți comanda? Pentru fiecare fel alegi o garnitură: 3 × 2 = 6 combinații. Produsul cartezian generează exact toate aceste combinații — câte un element din fiecare categorie.
Ce este produsul cartezian
Produsul cartezian a k mulțimi generează toate tuplurile formate luând câte un
element din fiecare mulțime. Pentru × : (1,a), (1,b), (2,a), (2,b).
Numărul de tupluri = produsul mărimilor: n₁ · n₂ · ... · n_k.
Generare prin recursie pe poziție
La fiecare poziție încerci toate valorile posibile, apoi treci la poziția următoare. Când ai completat toate pozițiile, ai un tuplu.
#include <iostream>
using namespace std;
int k, m; // k pozitii, fiecare cu valori 1..m
int sol[20];
void genereaza(int pas) {
if (pas == k) { // tuplu complet
for (int i = 0; i < k; i++) cout << sol[i] << " ";
cout << "\n";
return;
}
for (int val = 1; val <= m; val++) { // toate valorile la pozitia pas
sol[pas] = val;
genereaza(pas + 1);
}
}
int main() {
k = 2; m = 3;
genereaza(0); // 11 12 13 21 22 23 31 32 33
return 0;
}Pentru k = 2, m = 3 generează toate cele 3² = 9 perechi.
Spre deosebire de submulțimi (unde la fiecare element ramifici în „iau/nu iau"), aici la
fiecare poziție încerci toate valorile. Numărul de ramuri per pas e m, nu 2 — de
aceea ai mᵏ tupluri.
Mulțimi de mărimi diferite
Dacă pozițiile au valori din intervale diferite, ții limita fiecăreia separat:
int lim[20]; // lim[pas] = cate valori are pozitia pas
void genereaza(int pas) {
if (pas == k) { /* proceseaza */ return; }
for (int val = 1; val <= lim[pas]; val++) {
sol[pas] = val;
genereaza(pas + 1);
}
}Legătura cu numărarea în baze
Produsul cartezian cu k poziții și m valori e ca numărarea în baza m cu k cifre:
fiecare tuplu e un număr de la 00...0 la (m−1)(m−1)...(m−1). De aici și numărul mᵏ.
Complexitate
| Operație | Timp |
|---|---|
| generarea tuturor tuplurilor | O(mᵏ · k) |
Crește exponențial cu numărul de poziții → fezabil pentru k mic.
Capcane reale la produsul cartezian:
- Confuzi cu permutările: la produs cartezian valorile se pot repeta între poziții; la permutări, nu.
- Limite greșite pe poziții: la mulțimi de mărimi diferite, folosești aceeași limită pentru toate → tupluri lipsă sau în plus.
- Uiți cazul de bază: recursia nu se oprește la
pas == k. - Explozie pentru k mare: mᵏ crește exploziv; verifică limitele.
De reținut
- Produs cartezian = toate tuplurile cu câte un element din fiecare mulțime; mᵏ tupluri.
- Recursie pe poziție: la fiecare poziție încerci toate valorile (care se pot repeta).
- E ca numărarea în baza m cu k cifre; fezabil pentru k mic.