Produsul cartezian

Produsul cartezian $A\times B$ conține toate perechile ordonate $(a,b)$ cu $a\in A$ și $b\in B$. Dacă $A=\{1,2\}$ și $B=\{3,4\}$, rezultatele sunt $(1,3)$, $(1,4)$, $(2,3)$ și $(2,4)$. Dacă mulțimile au $m$ și $n$ elemente, produsul are $m\cdot n$ perechi.

Produsul cartezian al mulțimilor $A_1,A_2,\dots ,A_m$ este mulțimea tuturor șirurilor ordonate $(x_1,x_2,\dots ,x_m)$ cu $x_i\in A_i$. Numărul lui de elemente este produsul numerelor de elemente: $|A_1|\cdot |A_2|\cdots |A_m|$. Prin backtracking se generează cu un vector $x_1,\dots ,x_m$: pe nivelul $k$ se încearcă pe rând fiecare element al mulțimii $A_k$. Nu există o condiție suplimentară de continuare, deci orice prefix se poate extinde, iar fiecare șir apare o singură dată. Ordinea în care sunt încercate elementele fiecărei mulțimi determină ordinea de generare: ultimul nivel se schimbă cel mai des, ca la cifrele unui contor. Elementele pot fi egale pe poziții diferite, de aceea perechile $(1,1)$ și $(2,2)$ aparțin produsului $\{1,2\}\times \{1,2\}$. Dacă una dintre mulțimi este vidă, produsul este vid.

Exemplul 1 — $A_1=\{1,2\}$ și $A_2=\{1,2,3\}$. Vectorul n[k] memorează numărul de elemente ale mulțimii $A_k$, cu elementele $1,2,\dots ,n_k$.

#include <iostream>
using namespace std;
int x[10], n[10] = {0, 2, 3}, m = 2, nr = 0;
void bt(int k) {
    if (k > m) {
        cout << ++nr << ": " << x[1] << " " << x[2] << "\n";
        return;
    }
    for (int v = 1; v <= n[k]; ++v) {
        x[k] = v;
        bt(k + 1);
    }
}
int main() {
    bt(1);
    return 0;
}

Ordinea generării este $(1,1)$, $(1,2)$, $(1,3)$, $(2,1)$, $(2,2)$, $(2,3)$; a cincea soluție este $(2,2)$. În total sunt $2\cdot 3=6$ perechi, iar programul afișează liniile numerotate de la 1: 1 1 până la 6: 2 3.

Exemplul 2 — trei mulțimi și o restricție. Pentru $A_1=\{1,2,3\}$, $A_2=\{1,2\}$ și $A_3=\{1,2\}$ produsul are $3\cdot 2\cdot 2=12$ elemente. Dacă se cer doar tripletele în care $x_2\ne x_3$, condiția se verifică la nivelul 3: pentru fiecare valoare a lui $x_1$ (3 alegeri) și a lui $x_2$ (2 alegeri), $x_3$ are o singură valoare permisă, cea diferită de $x_2$. Rămân $3\cdot 2\cdot 1=6$ triplete: $(1,1,2)$, $(1,2,1)$, $(2,1,2)$, $(2,2,1)$, $(3,1,2)$ și $(3,2,1)$. Cu restricție, problema nu mai este un produs cartezian pur, dar se rezolvă cu același schelet, la care se adaugă o condiție de continuare.

Într-un produs cartezian cu $m$ mulțimi, ordinea generării se comportă ca un contor cu baze diferite: ultimul nivel parcurge toate valorile lui înainte ca penultimul să avanseze. Primul nivel avansează de $n_1$ ori, iar pentru fiecare valoare a lui se generează $n_2\cdot n_3\cdots n_m$ tupluri. În exemplul 2, tupluri cu $x_1=1$ sunt primele $2\cdot 2=4$ din cele 12, apoi urmează cele cu $x_1=2$ și cele cu $x_1=3$. De aceea poziția unui tuplu în ordinea de generare se calculează ca într-un sistem de numerație mixt. În exemplul 1, poziția perechii $(x_1,x_2)$, numerotată de la 1, este $(x_1-1)\cdot 3+x_2$: pentru $(2,2)$ se obține $1\cdot 3+2=5$, iar pentru $(2,3)$ se obține 6, adică ultima. Timpul de generare este proporțional cu numărul tuplurilor înmulțit cu lungimea lor.

Exemplul 3 — coduri. Un cod format din două litere (A, B) și o cifră (1, 2, 3) este un element al produsului $\{A,B\}\times \{A,B\}\times \{1,2,3\}$, cu $2\cdot 2\cdot 3=12$ coduri, de la AA1 la BB3. Literele se pot repeta, deci AA1 este un cod valid, spre deosebire de aranjamente, unde repetiția este interzisă.

Nu confunda produsul cartezian cu alegerea fără repetiție. Dacă $A=B=\{1,2\}$, perechile $(1,1)$ și $(2,2)$ sunt permise și există patru rezultate; aranjamentele de 2 din $\{1,2\}$ ar fi doar 2. Dacă una dintre mulțimi este vidă, produsul este vid. Când subiectul adaugă o restricție, numără pe niveluri: o restricție între două poziții se aplică la poziția mai mare dintre ele și reduce alegerile de pe acel nivel. Numărul de linii afișate de un program cu restricții nu este întotdeauna produsul dimensiunilor: depinde de câte valori sunt acceptate pe fiecare nivel, după ce nivelurile anterioare au fost fixate.

Exemplu în formatul examenului. Câte linii afișează programul de mai jos?

#include <iostream>
using namespace std;
int n[4] = {0, 3, 2, 2}, x[4];
void bt(int k) {
    if (k == 4) {
        cout << x[1] << x[2] << x[3] << "\n";
        return;
    }
    for (int v = 1; v <= n[k]; ++v)
        if (k < 3 || v != x[2]) {
            x[k] = v;
            bt(k + 1);
        }
}
int main() {
    bt(1);
    return 0;
}

• a) 6
• b) 9
• c) 12
• d) 24

Răspunsul corect este a). Mulțimile au 3, 2 și 2 elemente, deci fără restricție ar fi $3\cdot 2\cdot 2=12$ linii. Condiția k < 3 || v != x[2] acceptă la nivelul 3 numai valorile diferite de $x_2$, deci pe acel nivel rămâne o singură alegere. Numărul liniilor este $3\cdot 2\cdot 1=6$. Varianta c) este numărul tripletelor fără restricție.

Al doilea exemplu. Câte elemente are produsul $\{1,2,3\}\times \{a,b\}\times \{0,1\}$ și câte dintre ele încep cu 2? Produsul are $3\cdot 2\cdot 2=12$ elemente. Cele care încep cu 2 sunt $(2,a,0)$, $(2,a,1)$, $(2,b,0)$ și $(2,b,1)$, adică $1\cdot 2\cdot 2=4$ elemente: prima poziție are o singură valoare, iar celelalte rămân libere.

Greșeli frecvente

• Greșit: produsul cartezian cere elemente distincte pe poziții diferite.
  Corect: elementele se pot repeta; perechea $(1,1)$ aparține produsului $\{1,2\}\times \{1,2\}$.
• Greșit: numărul tuplurilor este suma numerelor de elemente.
  Corect: este produsul lor.
• Greșit: dacă una dintre mulțimi este vidă, produsul conține tuplul vid sau un tuplu parțial.
  Corect: produsul este vid.

Înainte și după