Ultimo aggiornamento: 2024-03-28
Scrivere un programma che, dato un intero \(n \geq 1\) passato sulla riga di comando, stampi il powerset dell’insieme \(X_n = \{0, 1, \ldots, n-1\}\). Il powerset è l’insieme dei sottoinsiemi di \(X_n\).
Ad esempio, se \(n = 3\), il programma deve produrre un output simile al seguente (l’ordine con cui i sottoinsiemi vengono elencati non è importante):
{ }
{ 2 }
{ 1 }
{ 1 2 }
{ 0 }
{ 0 2 }
{ 0 1 }
{ 0 1 2 }Il primo problema da risolvere è: come rappresentare un qualunque sottoinsieme di \(X_n = \{0, 1, \ldots, n-1\}\)? Il modo più semplice è di usare una bitmask (detto anche bit set), cioè un array binario di lunghezza \(n\). Un sottoinsieme \(A \subseteq \{0, 1, \ldots, n-1\}\) è rappresentato da \(n\) bit \(b_0, \ldots, b_{n-1}\) tali che:
\[ b_k = \begin{cases} 1 & \mbox{se}\ k \in A\\ 0 & \mbox{altrimenti} \end{cases} \]
Ad esempio, il sottoinsieme \(\{0, 3, 4\}\) di \(X_6\) è rappresentato dall’array \([1, 0, 0, 1, 1, 0]\).
Generare tutti i sottoinsiemi di \(X_n\) equivale quindi a enumerare tutte le possibili combinazioni di \(n\) bit: \([0, 0, \ldots, 0]\) equivale al sottoinsieme vuoto, mentre \([1, 1, \ldots, 1]\) equivale all’intero insieme \(X_n\).
Per generare tutte le possibili combinazioni di \(n\) bit \(b_0, \ldots, b_{n-1}\) è possibile utilizzare un algoritmo ricorsivo:
Si fissa \(b_0 = 0\), e si generano tutte le possibili combinazioni di \((n-1)\) bit \(b_1, \ldots, b_{n-1}\).
Successivamente, si fissa \(b_0 = 1\), e si generano tutte le possibili combinazioni di \((n-1)\) bit \(b_1, \ldots, b_{n-1}\).
La funzione powerset_ric(char *b, int i, int n) dovrebbe quindi avere il comportamento seguente:
Fissa \(b_i = 0\) e chiama powerset_ric(b, i+1, n) per generare tutte le permutazioni del sottovettore \(b_{i+1}, \ldots, b_{n-1}\), lasciando inalterati i valori \(b_0, \ldots, b_i\).
Successivamente, fissa \(b_i = 1\) e chiama powerset_ric(b, i+1, n) per generare tutte le permutazioni del sottovettore \(b_{i+1}, \ldots, b_{n-1}\), lasciando inalterati i valori \(b_0, \ldots, b_i\).
La funzione deve essere invocata inizialmente con powerset_ric(b, 0, n). Il caso base si ha quando \(i = n\), dove la funzione deve stampare l’elenco dei valori \(k\) per i quali \(b_k = 1\). Questo equivale a stampare il contenuto del sottovettore di \(X_n\) rappresentato dalla bitmask \(b_0, \ldots, b_{n-1}\).