Debruijnrij

Een debruijnrij is een begrip uit de combinatoriek. De debruijnrij ${\displaystyle B(k,n)}$ is een cyclisch gelezen rij (de beginelementen van de rij komen na het laatste element terug) waarin, gegeven een groep van ${\displaystyle k}$ objecten, alle mogelijke rijtjes van lengte ${\displaystyle n}$ van deze objecten precies één keer als deelrij voorkomen.

De rij ${\displaystyle B(k,n)}$ heeft de lengte ${\displaystyle k^{n}.}$ Er zijn ${\displaystyle {\frac {{k!}^{k^{n-1}}}{k^{n}}}}$ verschillende debruijnrijen ${\displaystyle B(k,n).}$

Debruijnrijen zijn vernoemd naar de Nederlandse wiskundige Nicolaas Govert de Bruijn. Hij onderzocht ze in een artikel dat in 1946 verscheen in de proceedings van de Koninklijke Nederlandse Akademie van Wetenschappen.^[1]

Een binaire debruijnrij van orde ${\displaystyle n}$ is een rij bits waarin elke mogelijke rij van ${\displaystyle n}$ bits precies eenmaal voorkomt. Een binaire debruijnrij van orde 3 is bijvoorbeeld de rij 0001011100. Cyclisch gelezen laat men de laatste ${\displaystyle n-1}$ bits weg, want deze zijn gelijk aan de eerste ${\displaystyle n-1}$ bits. De resterende bits kan men denkbeeldig in een cirkel plaatsen: {{0,0,0,1,0,1,1,1}}.

Binaire debruijnrijen bestaan voor elke orde ${\displaystyle n.}$ Het aantal binaire debruijnrijen van orde ${\displaystyle n}$ is ${\displaystyle 2^{2^{n-1}-n}}$; dit is voor ${\displaystyle n=1,2,3,4,5,\ldots }$ respectievelijk 1, 1, 2, 16, 2048, ...(rij A016031 in OEIS)

Debruijnrijen kunnen op verschillende manieren geconstrueerd worden: met behulp van De Bruijn-grafen, met combinatoriële algoritmen zoals het prefer-one-algoritme, met schuifregisters, enz.

Binaire debruijnrijen kunnen afgeleid worden uit een De Bruijn-graaf, dit is een gerichte graaf met ${\displaystyle 2^{n}}$ knopen die gelabeld zijn met de ${\displaystyle 2^{n}}$ rijen van ${\displaystyle n}$ bits. Er is een kant van knoop ${\displaystyle x}$ met binaire rij ${\displaystyle x_{1},\ldots ,x_{n}}$ naar knoop ${\displaystyle y}$ met binaire rij ${\displaystyle y_{1},\ldots ,y_{n}}$ als en slechts als ${\displaystyle y_{i}=x_{i+1}}$ voor ${\displaystyle i=1,\ldots ,n-1.}$ De rij in knoop ${\displaystyle y}$ bestaat dan uit de rij in knoop ${\displaystyle x}$ zonder de eerste bit en met een nieuwe laatste bit (0 of 1, die als label van de kant van ${\displaystyle x}$ naar ${\displaystyle y}$ kan dienen). Elke knoop heeft exact twee inkomende en twee uitgaande kanten.

Een De Bruijn-graaf is een Hamiltongraaf, en een debruijnrij komt overeen met een Hamiltonpad in de graaf. Dat is een gesloten pad dat elke kant in de graaf eenmaal bevat. Er is een 1-op-1-overeenkomst tussen de Hamiltonpaden in de De Bruijn-graaf van orde ${\displaystyle n}$ en de debruijnrijen van orde ${\displaystyle n+1}$

Om een debruijnrij op te maken aan de hand van een Hamiltonpad gaat men als volgt tewerk: Men noteert het label van de beginknoop en van iedere kant die men volgt noteert men het label (de nieuwe bit die wordt toegevoegd). Zo levert een Hamiltonpad in de De Bruijn-graaf van orde 3 hiernaast een debruijnrij van orde 4; vertrekkend vanuit knoop "110" leidt een mogelijk Hamiltonpad langs de kanten met labels 0→1→0→0→0→0→1→1→0→1→0→1→1→1→1→0, waardoor men de debruijnrij van orde 4 "1100100001101011110" verkrijgt.

Een eenvoudig algoritme om een de Bruijn-reeks te genereren is het "prefer-one"-algoritme:^[2]

1. (${\displaystyle n\geq 1}$) begin met een rij van ${\displaystyle n}$ nullen
2. Probeer een 1 toe te voegen als volgende bit. Als de laatste ${\displaystyle n}$ bits van de nieuwe rij nog niet eerder ontmoet werden: aanvaard de nieuwe rij en herhaal stap 2. Zo niet: ga naar de volgende stap.
3. Probeer een 0 toe te voegen als volgende bit. Als de laatste ${\displaystyle n}$ bits van de nieuwe rij nog niet eerder ontmoet worden: aanvaard de nieuwe rij en ga naar stap 2. Zo niet: stop.

Voor ${\displaystyle n=3}$ levert dit achtereenvolgens de rijen:

• 000
• 0001 (001 is nieuw)
• 00011 (011 is nieuw)
• 000111 (111 is nieuw)
• 0001110 (111 was oud, maar 110 is nieuw)
• 00011101 (101 is nieuw)
• 000111010 (011 was oud, maar 010 is nieuw)
• 0001110100 (100 is nieuw)
• ...stop (zowel 001 en 000 zijn oud).

Dit algoritme is gelijkaardig aan prefer-one, maar probeert in elke stap de bit toe te voegen die het complement is van de laatste bit in de rij, in plaats van een 1. Als dat niet lukt, probeert het dezelfde bit toe te voegen. Als dat nog niet lukt, stop het algoritme. Deze procedure levert echter nooit de rij van ${\displaystyle n}$ enen. Wanneer de rij eindigt op ${\displaystyle n-1}$ enen, voegen we er daarom een 1 aan toe. Het algoritme luidt dus:^[2]

1. (${\displaystyle n\geq 1}$) begin met een rij van ${\displaystyle n}$ nullen
2. Als de laatste bit van de huidige rij 0 is, probeer een 1 toe te voegen als volgende bit; zo niet probeer een 0. Als de laatste ${\displaystyle n}$ bits van de nieuwe rij nog niet eerder ontmoet werden: aanvaard de nieuwe rij en herhaal stap 2. Zo niet: ga naar de volgende stap.
3. Als de laatste bit van de huidige rij 0 is, probeer een 0 toe te voegen als volgende bit; zo niet, of als de laatste ${\displaystyle n-1}$ bits 1 zijn, probeer een 1. Als de laatste ${\displaystyle n}$ bits van de nieuwe rij nog niet eerder ontmoet worden: aanvaard de nieuwe rij en ga naar stap 2. Zo niet: stop.

Voor ${\displaystyle n=3}$ levert dit achtereenvolgens de rijen:

• 000
• 0001 (001 is nieuw)
• 00010 (010 is nieuw)
• 000101 (101 is nieuw)
• 0001011 (010 is oud maar 011 is nieuw)
• 00010111 (een 1 toegevoegd om 111 te hebben)
• 000101110 (110 is nieuw)
• 0001011100 (101 is oud maar 100 is nieuw)
• ...stop (zowel 001 als 000 zijn oud)