momente şi schiţe de informatică

Generarea directă a unor şiruri De Bruijn binare

Creat: 2014/jan       Comentarii

C++ | De Bruijn

Se cere un cel mai scurt cuvânt binar care să aibă ca subcuvinte toate secvenţele de n biţi.

Problema apare (cu formulări lungi) în V. Iorga, E. Kalisz, C. Ţăpuş - "Concursuri de programare", Ed. Teora 1997 (unde se identifică prin "Subşirurile distincte ale şirurilor de biţi"), sau în A. M. Iaglom, I. M. Iaglom - "Probleme neelementare tratate elementar", Ed. Tehnică 1983 (problema 125**).

Secvenţa S="0111000" are ca subcuvinte numerele de câte trei biţi 011, 111, 110, 100 şi 000. Dacă am prelungi S cu "0" - atunci "000" ar apărea de două ori ca subcuvânt şi nu am ajunge la un cel mai scurt cuvânt; cu acest raţionament va rezulta în final S="0111000101".

În termeni relativ moderni, avem de-a face cu şiruri De Bruijn (peste {0,1}) - dacă ignorăm ordinea "circulară" specifică acestora; astfel, pentru exemplul de mai sus, ultimii doi biţi devin inutili în cazul în care am cere "cel mai scurt cuvânt circular": dacă înscriem consecutiv pe un cerc S="01110001" (şir De Bruijn), atunci vedem şi secvenţa "liniară" (ceva mai lungă) redată iniţial.

Există însă chestiuni care necesită direct forma liniară: după introducerea primelor n cifre ale lui S, fiecare nouă tastare (0 sau 1) produce un nou număr de n biţi - presupunând că se reţin precedentele n-1 tastări; astfel că S poate servi pentru a repera într-un timp minim oricare cod prestabilit ("parolă") de n biţi. În exemplul de mai sus, n=3 iar S are lungimea 10; sunt suficiente 10 tastări pentru a găsi oricare parolă de 3 biţi - în loc de cele 24 de tastări care ar fi necesare dacă am neglija proprietatea dispozitivului de a reţine ultimele n-1 tastări şi am încerca pe rând câte unul dintre cele 8 coduri de câte 3 biţi (câte 3 tastări pentru fiecare cod = 24 tastări).

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.

Relaţia de derivare (înlănţuire) în $\mathbb{Z}_{2^n}$

$\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}$:

(1) $x_0=2^n-1$

(2) $i=1$

(3) $t=2\,(x_{i-1}\bmod 2^{n-1})$

(4) dacă $t\in\{x_0,\ldots,x_i\}$ atunci $t=t+1$

(5) $x_i=t$

(6) $i=i+1$

(7) dacă $i\leqslant 2^n-1$ atunci mergi la (3)

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$.

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.

Exemplificare pentru $\mathbb{Z_8}=\{0,1,2,3,4,5,6,7\}$ (n=3):

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.

Programul C++ următor implementează direct (dacă nu chiar mot-à-mot) cei doi algoritmi descrişi:

#include <iostream>
#include <vector>
#include <algorithm> // find( it_1, it_2, valoare )
#include <string>
#include <cmath>     // exp(), log(), log2()
#include <cstdlib>   // atoi()
using namespace std;

typedef vector<int> solution;
typedef solution::iterator cursor;

void bruijn(solution& sol, int n) { // Parcurgerea înlănţuită a resturilor modulo 2^n
    int n1 = exp(n*log(2)), // = 2^n -1
        m = (n1+1) >> 1;    // = 2^n/2 = 2^(n-1)
    sol.push_back(n1); // pasul (1)
    for(int i=1; i <= n1; ++i) {
        int t = (sol[i-1] % m) << 1; // pasul (3)
        if(find(sol.begin(), sol.end(), t) != sol.end()) // pasul (4)
            t += 1; 
        sol.push_back(t);         
    }
}
string binar(solution& sol) { // Reprezentarea minimală a mulţimii resturilor mod 2^n
    int n = log2(sol.size()); // sol[] are 2^n valori
    string seq(n, '1'); // începe cu '1..1' (n biţi)
    // înlănţuie cu biţii de paritate ai celorlalte valori
    for(cursor i=sol.begin()+1; i != sol.end(); ++i) 
        seq += (*i) & 1? '1':'0'; // extinde cu '1' sau '0', după paritate
    return seq;
}
int main(int argc, char** argv) {
    int n = argc==2? atoi(argv[1]):3;
    solution S;
    bruijn(S, n); 
    cout << binar(S) << '\n';
}
vb@vb:~$ ./bru 3
1110001011
vb@vb:~$ ./bru 4
1111000010011010111
vb@vb:~$ ./bru 5
111110000010001100101001110101101111

În şiruri De Bruijn#Algorithm este prezentată o funcţie Python recursivă bazată pe un algoritm mai complicat, dar care generează şiruri De Bruijn pentru orice alfabet şi nu numai pentru {0,1}, ca în cazul nostru.

Graful relaţiei de înlănţuire a resturilor modulo 2n

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ă.

Media Dinamică

Articolul 50

Drumuri

ŞahStartTemp

25
32
17
4
19
34
14
3
26
33
16
5
31
24
15
18
35
20
2
13
27
6
9
23
30
11
8
21
28
12
22
29
10
7

Ambiţiile Cavalerului

Localităţi

Judeţ:

Constituirea unei baze de date colectând cu Python de pe web

Bliţuri

Load another random Bliţ

//slightchess

Decoraţiuni hiperbolice

SALARII 2017

//bacMath
variante BAC matematică

Bacalaureat 2015 -
de la forma microsoftizată, la R

modelare ŞAH, I-XX
construcţia unui PGN-browser()

Linux şi aplicaţii Web
în 24 de ore

Orar şcolar - exemplu
după un orar generat de "aSc Orare"

Orar Adjust
ajustează orarul şcolar