Debruijnrij
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/De_Bruijn_sequence.svg/260px-De_Bruijn_sequence.svg.png)
Een debruijnrij is een begrip uit de combinatoriek. De debruijnrij is een cyclisch gelezen rij (de beginelementen van de rij komen na het laatste element terug) waarin, gegeven een groep van objecten, alle mogelijke rijtjes van lengte van deze objecten precies één keer als deelrij voorkomen.
De rij heeft de lengte Er zijn verschillende debruijnrijen
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]
Binaire debruijnrijen
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/De_bruijn_graph-for_binary_sequence_of_order_4.svg/260px-De_bruijn_graph-for_binary_sequence_of_order_4.svg.png)
Een binaire debruijnrij van orde is een rij bits waarin elke mogelijke rij van bits precies eenmaal voorkomt. Een binaire debruijnrij van orde 3 is bijvoorbeeld de rij 0001011100. Cyclisch gelezen laat men de laatste bits weg, want deze zijn gelijk aan de eerste 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 Het aantal binaire debruijnrijen van orde is ; dit is voor 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.
De Bruijn-graaf
Binaire debruijnrijen kunnen afgeleid worden uit een De Bruijn-graaf, dit is een gerichte graaf met knopen die gelabeld zijn met de rijen van bits. Er is een kant van knoop met binaire rij naar knoop met binaire rij als en slechts als voor De rij in knoop bestaat dan uit de rij in knoop zonder de eerste bit en met een nieuwe laatste bit (0 of 1, die als label van de kant van naar 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 en de debruijnrijen van orde
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.
Prefer-one-algoritme
Een eenvoudig algoritme om een de Bruijn-reeks te genereren is het "prefer-one"-algoritme:[2]
- () begin met een rij van nullen
- Probeer een 1 toe te voegen als volgende bit. Als de laatste 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.
- Probeer een 0 toe te voegen als volgende bit. Als de laatste bits van de nieuwe rij nog niet eerder ontmoet worden: aanvaard de nieuwe rij en ga naar stap 2. Zo niet: stop.
Voor 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).
Prefer-opposite-algoritme
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 enen. Wanneer de rij eindigt op enen, voegen we er daarom een 1 aan toe. Het algoritme luidt dus:[2]
- () begin met een rij van nullen
- 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 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.
- 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 bits 1 zijn, probeer een 1. Als de laatste bits van de nieuwe rij nog niet eerder ontmoet worden: aanvaard de nieuwe rij en ga naar stap 2. Zo niet: stop.
Voor 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)
- ↑ N.G. De Bruijn. "A combinatorial problem." Koninklijke Nederlandsche Akademie van Wetenschappen, Proceedings of the Section of Sciences, vol. XLIX, nrs. 6-10, blz. 758. Gearchiveerd op 21 oktober 2021.
- ↑ a b Abbas Alhakim. "A simple combinatorial algorithm for De Bruijn sequences." The American Mathematical Monthly (2010), vol. 117 nr. 8, blz. 728-732.