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

Binaire debruijnrijen

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, ...()

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:

() 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:

() 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)

Combinatoriek