Module: Itera su tutti i sottopattern di una data maschera


Problem

1 /7


Stringhe binarie di data lunghezza

Theory Click to read/hide

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.

Problem

Dato il numero N stampa tutte le stringhe di lunghezza N costituite da zero e uno in ordine lessicografico.

Per risolvere il problema, usa l'enumerazione di tutti i sottopattern.

Input

Viene dato il numero singolo N. (naturale, 1 ≤ N ≤ 10)

Uscita

È necessario stampare tutte le stringhe di lunghezza N costituite da zeri e uno in ordine lessicografico, una per riga

Input Uscita
2
00
01
10
11