Unione e intersezione combinano insiemi restando «allo stesso livello». Esistono però due costruzioni che producono insiemi nuovi e molto più grandi: l'insieme delle parti, che raccoglie tutti i sottoinsiemi, e il prodotto cartesiano, che forma tutte le coppie possibili. Sono alla base di concetti come relazioni, funzioni e spazi di configurazione, e spiegano perché certi problemi crescono così in fretta.
L'insieme delle parti
L'insieme delle parti di A, indicato con 𝒫(A) o 2ᴬ, è l'insieme di tutti i sottoinsiemi di A, compresi l'insieme vuoto e A stesso.
Se A = {r, w, x}:
𝒫(A) = {∅, {r}, {w}, {x}, {r, w}, {r, x}, {w, x}, {r, w, x}}
Gli elementi sono 8. In generale, se |A| = n, allora |𝒫(A)| = 2ⁿ.
Perché 2ⁿ
Costruire un sottoinsieme significa prendere, per ciascun elemento di A, una decisione binaria: dentro o fuori. Le decisioni sono n e indipendenti, quindi le combinazioni sono 2 · 2 · … · 2 = 2ⁿ.
Questo ragionamento suggerisce anche una rappresentazione molto pratica: un sottoinsieme di un insieme di n elementi si codifica con una stringa di n bit. Con l'ordine r, w, x, la stringa 101 rappresenta {r, x} e 000 l'insieme vuoto. È esattamente il modo in cui i permessi Unix sono memorizzati: lettura, scrittura ed esecuzione sono tre bit, e il permesso 5 in ottale, cioè 101 in binario, significa «lettura ed esecuzione».
Enumerare tutti i sottoinsiemi
La corrispondenza con i numeri binari dà subito un algoritmo:
def parti(elementi):
n = len(elementi)
for maschera in range(2 ** n):
yield {elementi[i] for i in range(n) if maschera >> i & 1}
list(parti(["r", "w", "x"]))
Il ciclo conta da 0 a 2ⁿ − 1 e, per ogni numero, include gli elementi corrispondenti ai bit accesi. Funziona bene finché n è piccolo: con 30 elementi i sottoinsiemi superano il miliardo. È il motivo per cui gli algoritmi che provano «tutte le combinazioni» diventano rapidamente impraticabili.
Il prodotto cartesiano
Il prodotto cartesiano di A e B è l'insieme di tutte le coppie ordinate (a, b) con a ∈ A e b ∈ B:
A × B = {(a, b) | a ∈ A, b ∈ B}
In una coppia ordinata l'ordine conta: (1, 2) ≠ (2, 1). E, a differenza degli insiemi, le ripetizioni sono ammesse: (3, 3) è una coppia valida.
Se A = {S, M, L} (taglie) e B = {nero, bianco} (colori):
A × B = {(S, nero), (S, bianco), (M, nero), (M, bianco), (L, nero), (L, bianco)}
Le coppie sono 3 · 2 = 6. In generale |A × B| = |A| · |B|.
Più di due fattori
Il prodotto si estende a n insiemi, producendo n-uple: A₁ × A₂ × … × Aₙ. Una riga di una tabella di database con tre colonne è un elemento di D₁ × D₂ × D₃, dove Dᵢ è il dominio dei valori di ciascuna colonna. Il piano cartesiano è ℝ × ℝ, e un indirizzo IPv4 è un elemento di {0, …, 255}⁴, insieme che ha 256⁴ = 2³² elementi.
Il prodotto cartesiano in SQL
Una CROSS JOIN tra due tabelle produce esattamente il prodotto cartesiano delle loro righe. Con tabelle da 1.000 e 2.000 righe si ottengono 2 milioni di righe. Una JOIN scritta dimenticando la condizione di collegamento ha lo stesso effetto, ed è un errore classico che fa esplodere i tempi di esecuzione di una query.
Prodotto cartesiano e test
Quando un software ha diversi parametri di configurazione, lo spazio di tutte le configurazioni è il loro prodotto cartesiano. Con un sistema operativo tra 3, un browser tra 4 e una lingua tra 5, le combinazioni sono 3 · 4 · 5 = 60.
Testarle tutte è possibile; con dieci parametri da cinque valori ciascuno non lo è più (5¹⁰ è quasi dieci milioni). Per questo si usano tecniche come il pairwise testing: si sceglie un sottoinsieme del prodotto cartesiano in cui ogni coppia di valori di parametri diversi compare almeno una volta. Molti difetti dipendono dall'interazione di due soli parametri, e questo approccio li cattura con un numero di test molto minore.
Insieme delle parti e prodotto a confronto
| Insieme delle parti | Prodotto cartesiano | |
|---|---|---|
| Elementi | sottoinsiemi di A | coppie (a, b) |
| Cardinalità | 2ⁿ | n · m |
| Crescita | esponenziale | polinomiale |
| Esempio | combinazioni di permessi | varianti di un prodotto |
C'è anche un legame profondo: una relazione tra A e B si definisce come un sottoinsieme di A × B, cioè un elemento di 𝒫(A × B). Le relazioni possibili tra due insiemi da 3 elementi sono quindi 2⁹ = 512.
In sintesi
- L'insieme delle parti contiene tutti i sottoinsiemi e, se |A| = n, ha 2ⁿ elementi.
- Ogni sottoinsieme si codifica con n bit, come i permessi Unix.
- Il prodotto cartesiano contiene tutte le coppie ordinate e ha |A| · |B| elementi.
- Una CROSS JOIN, o una JOIN senza condizione, produce il prodotto cartesiano delle righe.
- Una relazione è un sottoinsieme del prodotto cartesiano.
