Mai jos studiem o relaţie "$u\succcurlyeq v$" între numere reprezentabile pe n biţi, astfel încât $u$ şi $v$ să poată fi reperate într-o secvenţă de n+1 biţi consecutivi dintr-un şir S; justificăm un algoritm de generare a unui şir finit de numere naturale - prin iterarea relaţiei "$u\succcurlyeq v$" - astfel încât reprezentările binare ale termenilor şirului să poată furniza un cuvânt S cu proprietăţile cerute.
Şirul generat prin acest algoritm coincide cu cel dat de parcurgerea DFS a grafului asociat relaţiei "$u\succcurlyeq v$", plecând însă dintr-un anumit nod al acestuia.

$\mathbb{Z}_{2^n}=\{0,1,2,\ldots,2^n-1\}$ conţine toate numerele naturale reprezentabile pe un registru cu $n\,(\geqslant 2)$ poziţii binare. Dacă $u, v \in \mathbb{Z}_{2^n}$ spunem că $v$ "derivează" din $u$ şi scriem $u\succcurlyeq v$ dacă primii n-1 biţi ai lui $v$ coincid cu ultimii n-1 biţi ai lui $u$.

De exemplu, în $\mathbb{Z}_{8}$ avem succesiv 3(=011) $\succcurlyeq$ 7(=111) $\succcurlyeq$ 6(=110) $\succcurlyeq$ 4(100), ş.a.m.d. "Derivarea" este analogă instrucţiunii rcl AX, 1 - prin care microprocesorul deplasează spre stânga cu o poziţie conţinutul registrului AX şi preia valoarea curentă din "carry flag" în bitul de rang 0 al lui AX (în plus, "carry flag" este înscris în final cu bitul "ieşit" din AX prin deplasare). Microprocesorul operează cu regiştri de 8/16/32/64 biţi - "derivarea" introdusă mai sus este mai generală.

Lemă Dacă $u,v\in\mathbb{Z}_{2^n}$ atunci:

(a) $u\succcurlyeq v \Leftrightarrow v=2\,(u\bmod 2^{n-1})+\alpha,\,\alpha\in\{0,1\}$;

(b) $u\succcurlyeq u \Leftrightarrow u\in\{0,2^n-1\}$;

(c) dacă $u,v\in\mathbb{Z}_{2^n}\setminus\{0,2^n-1\}$ atunci:

$((u\succcurlyeq v)$ şi $(v\succcurlyeq u)) \Leftrightarrow u+v=2^n-1$ şi $u=\begin{cases}\dfrac{2^{n+1}-2}{3},&n\text{ par}\\\\ \dfrac{2^{n+1}-1}{3},&n\text{ impar}\end{cases}$

(d) $u\succcurlyeq v \Leftrightarrow \tilde{u} \succcurlyeq \tilde{v}$, unde $\tilde{x}$ complementează biţii din $x$ ($\tilde x = (2^n-1)-x$, pentru $x\in\mathbb{Z_{2^n}}$)

Demonstraţie

(a) Dezvoltarea $u=\overline{u_1u_2\ldots u_n}=u_1\,2^{n-1}+(u_2\,2^{n-2}+\cdots+u_n)$ arată că $u_1$ şi $\overline{u_2\ldots u_n}$ sunt câtul şi restul împărţirii lui $u$ prin $2^{n-1}$; avem $u\succcurlyeq v \Leftrightarrow v=2\,\overline{u_2\ldots u_n}+\alpha=2\,(u\bmod 2^{n-1})+\alpha$.

(b) $u\succcurlyeq u \Leftrightarrow 2\,(u\bmod 2^{n-1})+\alpha=u \Leftrightarrow 2\,(u-u_1 2^{n-1})+\alpha=u \Leftrightarrow u=u_1 2^n - \alpha$ şi avem $u\in\mathbb{Z}_{2^n} \Leftrightarrow (u_1=0,\alpha=0)\text{ sau }(u_1=1, \alpha=1)$ - adică $u=0$ sau $u=2^n-1$.

(c) Din $u=\overline{u_1u_2\ldots u_n}\succcurlyeq v=\overline{u_2\ldots u_n\alpha_1} \succcurlyeq \overline{u_3\ldots u_n\alpha_1\alpha_2}=u$ obţinem $u_1=u_3=u_5=\ldots$ şi $u_2=u_4=u_6=\ldots$ şi cum $u\neq v$ (fiindcă la (c) sunt excluse valorile vizate de (b)) - urmează că avem $u=\overline{10101\ldots}$ şi $v=\overline{01010\ldots}$ (câte $n$ biţi); rezultă $u+v=2^n-1$ şi $u$ este suma unei progresii geometrice de raţie $2^2$, cu primul termen 1 sau 2, după paritatea lui n.

(d) Fie $u=\overline{u_1u_2\ldots u_n}\succcurlyeq v=\overline{u_2u_3\ldots u_n\alpha}$. Avem $\tilde{u}=\overline{\tilde{u_1}\tilde{u_2}\ldots\tilde{u_n}}$ şi evident $\tilde{u}\succcurlyeq\overline{\tilde{u_2}\ldots\tilde{u_n}\tilde{\alpha}}=\tilde{v}$.

Parcurgerea înlănţuită a resturilor modulo $2^n$

Teoremă. Următorul algoritm generează şirul $x_0,x_1,\ldots,x_{2^n-1}$ astfel încât $\{x_0,x_1,\ldots,x_{2^n-1}\}=\mathbb{Z_{2^n}}$ şi $x_0\succcurlyeq x_1\succcurlyeq x_2\succcurlyeq \ldots\succcurlyeq x_{2^n-1}$:

Demonstraţie

După (1) avem $x_0=2^n-1=\overline{1\ldots 1}$; urmând (2)..(5) obţinem $x_1=\overline{1\ldots 10}=2^n-2\neq x_0$.

Să presupunem că până la un anumit $i\lt 2^n-1\,(i\gt 1)$ s-a construit prin (3)..(7) mulţimea $\Gamma=\{x_0,x_1,\ldots,x_i\}$, cu $x_j\neq x_k\,(0\leqslant j,k\leqslant i,\,j\neq k)$ şi - conform cu (3),(4) şi cu Lema (a) - $x_0\succcurlyeq x_1\succcurlyeq \ldots \succcurlyeq x_i$. Fie acest $x_i=\overline{\alpha_1\alpha_2\ldots\alpha_n}$.

Continuând atunci la (3), $t=2\,(x_i \bmod 2^{n-1})$ şi avem $x_i\succcurlyeq t$; să demonstrăm că sau $t$ sau $t+1$ poate fi adăugat în $\Gamma$ - adică sau $t$ sau $t+1$, nu coincide cu nici un $x_j,\,j\leqslant i$.

Să presupunem contrariul, deci $t=\overline{\alpha_2\ldots\alpha_n 0} = x_k\in\Gamma$ şi $t+1=\overline{\alpha_2\ldots\alpha_n 1}=x_j\in\Gamma$, cu $0\leqslant k,j\leqslant i,\,k\neq j$. Dar avem $k\neq 0$, dat fiind că $x_0$ şi $x_k$ diferă cel puţin la bitul de rang 0; întrucât $x_{k-1}\succcurlyeq x_k$, avem $x_{k-1}=\overline{\xi\alpha_2\ldots\alpha_n}$, pentru un anumit $\xi\in\{0,1\}$ şi deoarece $x_{k-1}\neq x_i$ urmează că $\xi=1-\alpha_1$ - adică avem $x_{k-1}=\overline{\tilde{\alpha_1}\alpha_2\ldots\alpha_n}$.

Presupunând acum şi $j\neq 0$, deoarece $x_{j-1}\succcurlyeq x_j$ avem $x_{j-1}=\overline{\eta\alpha_2\ldots\alpha_n}$ şi cum $x_{j-1}\neq x_j$, rezultă $\eta=\tilde{\alpha_1}$ - dar atunci am obţine $x_{j-1}=x_{k-1}$, contradicţie cu presupunerea iniţială (că valorile din $\Gamma$ sunt distincte şi sunt "înlănţuite" până la rangul $i$).

Rămâne ca singura posibilitate, $j=0$. Deci $t+1=x_0=\overline{11\ldots 1}$, deci $x_i=\overline{\alpha_1 11\ldots 1}$; cum $x_i\in\Gamma$, urmează că $\alpha_1=0$ (altfel am obţine $x_i=x_0$, contradicţie).

Rezultă că lista $\Gamma$ va putea fi prelungită prin trecerea repetată (3)..(7) fie cu $t$, fie cu $t+1$, fără a se obţine un duplicat - pănă când se va găsi valoarea $x_i=\overline{011\ldots 1}$; această valoare finală este sigur atinsă, fiindcă $\Gamma$ conţine elemente, distincte două câte două, din $\mathbb{Z_{2^n}}$ (care este finită).

Deci algoritmul construieşte lista $\Gamma=\{x_0=\overline{11\ldots 1},x_1,x_2,\ldots,x_p=\overline{011\ldots 1}\}$ şi rămâne să mai dovedim că $p=2^n-1$; pentru aceasta, vom arăta că $\forall u\in\mathbb{Z_{2^n}},\,\exists i\in\{0,\ldots,p\}$ astfel încât $x_i=u$.

Va fi suficient să demonstrăm că $\Gamma$ conţine orice număr impar din $\mathbb{Z_{2^n}}$, pentru că - prin (3) şi (4) - un număr impar va fi ales în $\Gamma$ numai dacă numărul inferior (par) există deja în $\Gamma$.

Deja ştim că numerele impare $\overline{\alpha 11\ldots 1},\,\alpha\in\{0,1\}$ există în $\Gamma$ ($x_0$ şi $x_p$). Să arătăm că $\Gamma$ conţine şi toate numerele impare $\overline{\alpha_1\alpha_2 11\ldots 1},\,\alpha_1,\alpha_2\in\{0,1\}$; dacă $\alpha_2=1$, atunci aceste numere sunt $x_0$ şi $x_p$ şi rămân situaţiile $(\alpha_1,\alpha_2)\in\{(1,0),(0,0)\}$.

Deoarece $x_p=\overline{011\ldots 1}$ şi $x_{p-1}\succcurlyeq x_p$, urmează că $x_{p-1}=\overline{\xi 011\ldots 1},\,\xi\in\{0,1\}$. Deoarece $x_p$ este impar, valoarea pară $x_p-1$ deja există în $\Gamma$, fie ea $x_q=\overline{011\ldots 10}\in\Gamma$; atunci $x_{q-1}=\overline{\eta 011\ldots 1}$ şi cum $x_{p-1}\neq x_{q-1}$ rezultă că $\xi\neq\eta$, adică în $\Gamma$ avem şi $\overline{\alpha_1\alpha_2 11\ldots 1},\,(\alpha_1,\alpha_2)\in\{(1,0),(0,0)\}$.

Presupunem acum că pentru un $k,\,2\leqslant k\lt n-2$, avem $\overline{\alpha_1\alpha_2\ldots\alpha_k 011\ldots 1}\in\Gamma,\,\forall \alpha_i\in\{0,1\}$, $i=1..k$; să demonstrăm că în această ipoteză, avem şi $\overline{\xi\alpha_1\alpha_2\ldots\alpha_k 01\ldots 1}\in\Gamma,\,\xi\in\{0,1\}$.

Deoarece $\overline{\alpha_1\alpha_2\ldots\alpha_k 011\ldots 1}=x_j\in\Gamma$ şi este impar, urmează că şi $\overline{\alpha_1\alpha_2\ldots\alpha_k 011\ldots 10}=x_q\in\Gamma$ (ca fiind valoarea pară care precede pe $x_j$); atunci $x_{q-1}=\overline{\xi\alpha_1\alpha_2\ldots\alpha_k 011\ldots 1}\in\Gamma$ pentru un anumit $\xi\in\{0,1\}$, iar $x_{j-1}=\overline{\eta\alpha_1\alpha_2\ldots\alpha_k 01\ldots 1}\in\Gamma$ pentru un $\eta\in\{0,1\}$. Cum $x_{j-1}\neq x_{q-1}$, urmează $\eta\neq\xi$ - adică în $\Gamma$ apar toate numerele $\overline{\xi\alpha_1\alpha_2\ldots\alpha_k 01\ldots 1},\,\xi\in\{0,1\}$, ceea ce (conform principiului inducţiei matematice) încheie demonstraţia.

calcule în paşii (3)-(5)          lista Γ
                                  7
2*(7 mod 4) = 2*3 = 6             7, 6
2*(6 mod 4) = 2*2 = 4             7, 6, 4
2*(4 mod 4) = 0                   7, 6, 4, 0
2*(0 mod 4) = 0 ∈ Γ               7, 6, 4, 0, 1
2*(1 mod 4) = 2                   7, 6, 4, 0, 1, 2
2*(2 mod 4) = 4 ∈ Γ               7, 6, 4, 0, 1, 2, 5
2*(5 mod 4) = 2 ∈ Γ               7, 6, 4, 0, 1, 2, 5, 3
STOP: Γ are exact 8 elemente.

Lanţul obţinut $7\succcurlyeq 6\succcurlyeq 4\succcurlyeq 0\succcurlyeq 1\succcurlyeq 2\succcurlyeq 5\succcurlyeq 3$ conduce la permutarea circulară $\left(\begin{matrix}0&1&2&3&4&5&6&7\\1&2&5&7&0&3&4&6\end{matrix}\right)$ şi în fond, vedem următoarea consecinţă interesantă:

Consecinţă: Grupul permutărilor peste $\mathbb{Z_{2^n}}$ conţine (cel puţin) două permutări $\psi$ circulare încât $\psi(0)=1$ şi $\psi(k)\in\{2\,(\psi(k-1)\bmod 2^{n-1}),\,2\,(\psi(k-1)\bmod 2^{n-1})+1\},\,k=1..2^n-1$.

De ce două permutări (şi nu una, având un singur şir)?

Proprietatea din Lemă (d) ne spune că relaţia de înlănţuire $\succcurlyeq$ se menţine prin complementarea valorilor respective, astfel că obţinând prin algoritmul de mai sus $x_0\succcurlyeq x_1\succcurlyeq\ldots\succcurlyeq x_{2^n-1}$ - avem imediat încă un astfel de şir - complementând faţă de $2^n-1$ termenii primului şir.

Astfel, din şirul $7\succcurlyeq 6\succcurlyeq 4\succcurlyeq 0\succcurlyeq 1\succcurlyeq 2\succcurlyeq 5\succcurlyeq 3$ găsit în exemplificarea de mai sus, găsim prin complementarea termenilor faţă de 7, şirul $0\succcurlyeq 1\succcurlyeq 3\succcurlyeq 7\succcurlyeq 6\succcurlyeq 5\succcurlyeq 2\succcurlyeq 4$ (care conduce la o a doua permutare circulară cu proprietăţile menţionate în "Consecinţă").

Să observăm că algoritmul este liniar: lista $\Gamma$ este extinsă continuu, fără nici un abandon (fără "backtracking"); este drept însă că extinderea necesită un test prealabil (pasul (4)) asupra unuia dintre cele două numere posibile în momentul respectiv (perturbând oarecum, "liniaritatea").

Reprezentarea binară minimală a lui $\mathbb{Z_{2^n}}$

Teorema de mai sus ne permite să găsim uşor două cele mai scurte cuvinte binare, fiecare acoperind toate secvenţele posibile de acelaşi număr de biţi: fie $x_0,x_1,\ldots,x_{2^n-1}$ şirul obţinut prin algoritmul de mai sus; fie $\overline{\alpha_1\alpha_2\ldots\alpha_n}$ reprezentarea binară a lui $x_0$ şi pentru $i\geqslant 1$, fie $e_i=(x_i\bmod 2)$. Atunci cuvântul binar $\overline{\alpha_1\ldots\alpha_ne_1e_2\ldots e_{2^n-1}}$ are ca subcuvinte, fără repetiţie, toate secvenţele posibile de câte $n$ biţi; inversând fiecare bit, găsim - conform Lemă (d) - un al doilea astfel de cuvânt.

Într-adevăr, $e_i$ este ultimul bit (cel de paritate) al reprezentării binare a lui $x_i$; cum $x_0\succcurlyeq x_1$, urmează că $\overline{\alpha_2\ldots\alpha_n e_1}=x_1$; la fel, $x_1\succcurlyeq x_2$ atrage $\overline{\alpha_3\ldots\alpha_n e_1e_2}=x_2$; ş.a.m.d.

Considerăm graful orientat $\mathbb{B}_n=(\mathbb{Z}_{2^n},\mathsf{E})$, unde $(u,v)\in\mathsf{E}\Leftrightarrow u\succcurlyeq v$, cu $u,v\in\mathbb{Z}_{2^n}$. Din definiţia relaţiei $u\succcurlyeq v$ şi din Lemă (b),(c) rezultă imediat următoarele proprietăţi ale acestui graf:
- există două (şi numai două) bucle: $(0,0)$ şi $(2^n-1,2^n-1)$;
- orice vârf $u$ pentru care $(u,u)\notin\mathsf{E}$ are $d^{-}(u)=d^{+}(u)=2$ (gradele vârfului);
- există un singur "arc dublu", adică există $u,v\in\mathbb{Z}_{2^n},\,u\neq v$ unice încât $(u,v)\in\mathsf{E}$ şi $(v,u)\in\mathsf{E}$.

$\mathbb{B}_n$ este un caz particular de graf de Bruijn; circuitele hamiltoniene ale acestor grafuri reprezintă exact şirurile de Bruijn construite peste un alfabet dat (în particular, pe $\{0,1\}$ - caz în care proprietatea tocmai menţionată se deduce direct din cele prezentate mai sus).

Algoritmul din Teorema de mai sus exprimă în fond o parcurgere DFS a grafului $\mathbb{B}_n$: la pasul (3) se determină un nod adiacent celui curent, iar la pasul (4) se testează dacă acesta a mai fost vizitat (caz în care se consideră celălalt adiacent al nodului curent). Ceea ce este demonstrat în teorema pomenită este faptul că se poate avansa astfel până ce sunt vizitate toate vârfurile - garantând că DFS($2^n-1$) va produce nodurile în ordinea dată de relaţia $\succcurlyeq$ (ceea ce nu mai are loc în general, dacă startăm DFS dintr-un alt nod iniţial).

Apare astfel ideea unui alt tip de implementare: derivăm "Bgraph" dintr-o clasă preexistentă "Graph" (unde avem de regulă şi o metoda DFS()), astfel încât constructorul de obiecte "Bgraph" să constituie adiacenţa impusă de relaţia $\succcurlyeq$; prevedem în "Bgraph" o metodă care să invoce Graph::DFS(V-1) (unde V=2^n este numărul de vârfuri) şi să afişeze nodurile parcurse. Conform celor tocmai evidenţiate mai sus, vom obţine ca rezultat şirul De Bruijn construit în teorema demonstrată la început - dar (spre deosebire de implementarea "directă", din programul de mai sus) fără a folosi în mod explicit şi algoritmul preconizat acolo.

Formularea unei astfel de metode (afişează nodurile parcurse prin DFS()) este cum nu se poate mai banală, dar conceperea în ansamblu a lucrurilor (începând chiar cu o definiţie acceptabilă şi adecvată derivării, pentru clasa "Graph") poate fi instructivă şi merită o abordare separată.