Module: Itera su tutti i sottopattern di una data maschera

Succede che è necessario enumerare tutte le sequenze di bit di una certa lunghezza. In altre parole, itera su tutte le opzioni possibili, dove per ogni oggetto viene selezionato uno dei due stati possibili.

In tali situazioni, è possibile implementare l'enumerazione utilizzando maschere di bit. Il vantaggio di questo approccio è che tale codice funziona in modo non ricorsivo e opera su numeri invece che su raccolte o simili, il che migliora notevolmente le prestazioni.

Di seguito è riportato il codice generale che utilizza le maschere di bit: int; // numero di oggetti (lunghezza della sequenza di bit) for (int mask = 0; mask < (1 << n); mask++) { // scorre tutti i numeri da 0 a 2^n - 1, dove ogni numero corrisponde a una maschera di bit // la maschera del numero corrente è una maschera di bit, dove l'i-esimo bit specifica lo stato dell'i-esimo oggetto for (int i = 0; i < n; i++) { // itera su n bit per capire quale stato ha ogni oggetto if ((1 << i) & mask) { // controlla se l'i-esimo bit è uguale a uno // elabora l'opzione che l'i-esimo oggetto ha lo stato '1' } else { // caso in cui l'i-esimo bit è zero // elabora l'opzione che l'i-esimo oggetto dello stato '0' } } }
Questo codice viene eseguito in O(2^n * f(n)), dove f(n) è il tempo necessario per elaborare un particolare iterabile.