de Bruijn-sekvens

Inom kombinatoriken är en k-när de Bruijn-sekvens B(k, n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje möjlig delsekvens av längden n uppträder en och endast en gång som på varandra följande tecken. Sekvensen är uppkallad efter den holländske matematikern Nicolaas Govert de Bruijn.

De Bruijn-sekvensen för k = 2 och n = 2. Den cykliska sekvensen 0011 innehåller alla två tecken långa strängar som kan bildas ur alfabetet {0,1}, d.v.s 00, 01, 10 och 11.

Varje B(k, n) har längden kⁿ.

Det finns ${\dfrac {\left(k!\right)^{k^{n-1}}}{k^{n}}}$ skilda de Bruijn-sekvenser B(k, n).

Enligt de Bruijn själv bevisades existensen av de Bruijn-sekvenser för alla ordningar med ovanstående egenskaper först för alfabet med två bokstäver av Camille Flye Sainte-Marie 1894, medan utvidgningen till större alfabeten är ett verk av Tanja van Aardenne-Ehrenfest och honom själv.

Historia

Det tidigaste kända exemplet på en de Bruijn-sekvens kommer från sanskritsprosodi. Sedan Pingalas arbeten har varje möjligt trestavigt mönster av långa och korta vokaler ett namn i form av en konsonant: som "y" för kort-lång-lång och "r" för lång-kort-lång. För att komma ihåg dessa namn, används minnesramsan yamātārājabhānasalagām, i vilken varje trestavigt mönster inleds av sitt "konsonantnamn": yamātā har alltså ett kort-lång-lång-mönster, rājabhā lång-kort-långt, och så vidare. Denna minnesramsa, som är ekvivalent med en de Bruijn-sekvens av binära tripplar (0111010001 vilket motsvarar 11101000, med tillägg av första och sista tecknet i andra änden 0+11101000+1 för att kompensera för att ramsan är linjär och ej cyklisk), är av okänd ålder men är åtminstone lika gammal som C. P. Browns bok från 1869 om versmått på sanskrit som nämner den.

I ett nummer av den franska pusseltidskriften L'Intermédiaire des Mathématiciens ställde A. de Rivière 1894 frågan om det fanns ett sätt att arrangera alla $2^{n}$ binärsekvenser av längden n i en cirkulär sträng med längden $2^{n}$. Problemet löstes, tillsammans med räkningen av antalet lösningar $2^{2^{n-1}-n}$, av C. Flye Sainte-Marie samma år. Detta glömdes dock mer eller mindre bort och Martin (1934) bevisade existensen av sådana cykler för generella storlekar av alfabet andra än två. Slutligen, när K. Posthumus ställde antagandet att antalet binära sekvenser var $2^{2^{n-1}-n}$, bevisade de Bruijn antagandets riktighet 1946, genom vilket problemet blev välkänt.

Karl Popper beskriver oberoende dessa binärsekvenser i avsnitt 55 av sin Logik der Forschung (1934) och kallar dem n-Nachwirkungsfreie Alternativen och ger även formeln för deras antal.

De Bruijn skriver att "motsvarande räkningsproblem för ett alfabet med σ bokstäver verkar först ha ställts och lösts 1951" och avser då van Aardenne-Ehrenfest, de Bruijn (1951).

Exempel

• För A = {0, 1} finns det två distinkta B(2, 3): 00010111 och 11101000. Den ena är en negation eller spegling av den andra.
• Två av de 2048 möjliga B(2, 5) i samma alfabet är 00000100011001010011101011011111 och 00000101001000111110111001101011.

Konstruktion

de Bruijn-sekvenser kan konstrueras genom att ta en Hamiltonväg på en n-dimensionell de Bruijn-graf över k tecken (eller, likvärdigt, en Eulercykel på en (n − 1)-dimensionell de Bruijn-graf).

En alternativ konstruktion kan åstadkommas genom att konkatenera alla Lyndonord som har en längd som delar n i lexikografisk ordning. Se artikeln om Lyndonord för en närmare beskrivning.

de Bruijn-sekvenser kan också skapas genom att använda skiftregister eller via ändliga kroppar.

Exempel

En de Bruijn-graf. Varje fyrsiffrig sekvens förekommer en och endast en gång om man färdas längs varje kant (båge) en och endast en gång och återvänder till startpunkten (en Eulercykel). Varje tresiffrig sekvens förekommer en och endast en gång om man passerar varje hörn (nod) en och endast en gång (en Hamiltonväg). Notera att det är en riktad graf, där varje hörn har en kant 0 och en kant 1 som leder från det och till det hörn som betecknas med den tresiffriga sekvens som blir resultatet om man lägger till 0 eller 1 i slutet och stryker första siffran.

Mål: Att konstruera en B(2, 4) de Bruijn-sekvens med längden 2⁴ = 16 genom en Eulercykel på den (n − 1 = 4 − 1 = 3) tredimensionella de Bruin-graf som avbildas i figuren till höger. Notera att det leder två riktade kanter från varje hörn (och även två till varje hörn).

Varje kant (båge) i denna tredimensionella de Bruijn-graf motsvarar en sekvens på fyra siffror: de tre siffror som betecknar hörnet (noden) som kanten lämnar följda av den siffra som betecknar kanten. Om man från hörnet 000 färdas längs kanten betecknad 1 kommer man till hörnet 001 och får delsekvensen 000+1=0001 i de Bruijn-sekvensen (notera att hörnet 001, nästa utgångspunkt avslutar 0001). Att färdas längs alla sexton kanterna en och endast en gång innebär att man använder sig av varje av de sexton fyrsiffriga sekvenserna exakt en gång vardera, vilket genererar en de Bruijn-sekvens.

Om vi till exempel följer en Eulerkrets genom hörnen i denna ordning...

000, 000, 001, 011, 111, 111, 110, 101, 011,

110, 100, 001, 010, 101, 010, 100, 000.

..blir detta våra överlappande, och unika, fyrsiffriga sekvenser:

0 0 0 0

_ 0 0 0 1

_ _ 0 0 1 1

_ _ _ 0 1 1 1

etcetera

Vilket resulterar i denna de Bruijn-sekvens:

0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1

Nedan markeras med {X X X} hur de åtta hörnen passeras (de unika fyrsiffriga sekvenserna får man genom att lägga till siffran efter hörnet, som ju är vilken kant man följer från hörnet - notera också att man lämnar hörnet den ena gången längs ena kanten och den andra gången längs den andra, till exempel {0 0 0} 0 respektive {0 0 0} 1).

      {0  0  0} 0  1  1  1  1  0  1  1  0  0  1  0  1
       0 {0  0  0} 1  1  1  1  0  1  1  0  0  1  0  1
       0  0 {0  0  1} 1  1  1  0  1  1  0  0  1  0  1
       0  0  0 {0  1  1} 1  1  0  1  1  0  0  1  0  1
       0  0  0  0 {1  1  1} 1  0  1  1  0  0  1  0  1
       0  0  0  0  1 {1  1  1} 0  1  1  0  0  1  0  1
       0  0  0  0  1  1 {1  1  0} 1  1  0  0  1  0  1
       0  0  0  0  1  1  1 {1  0  1} 1  0  0  1  0  1
       0  0  0  0  1  1  1  1 {0  1  1} 0  0  1  0  1
       0  0  0  0  1  1  1  1  0 {1  1  0} 0  1  0  1
       0  0  0  0  1  1  1  1  0  1 {1  0  0} 1  0  1
       0  0  0  0  1  1  1  1  0  1  1 {0  0  1} 0  1
       0  0  0  0  1  1  1  1  0  1  1  0 {0  1  0} 1
       0  0  0  0  1  1  1  1  0  1  1  0  0 {1  0  1}
   ... 0} 0  0  0  1  1  1  1  0  1  1  0  0  1 {0  1 ...
   ... 0  0} 0  0  1  1  1  1  0  1  1  0  0  1  0 {1 ...

...och vi är tillbaka vid utgångspunkten. Varje av de åtta tresiffriga sekvenserna (motsvarande de åtta hörnen) förekommer exakt två gånger och varje av de sexton fyrsiffriga sekvenserna (motsvarande de sexton kanterna) förekommer exakt en gång.

Algoritm

Man kan bilda en de Bruijn-sekvens genom konkatenering i lexikografisk ordning av alla Lyndonord med en längd som delar n. Det finns en algoritm som genererar alla Lyndonord med längder upp till och med n i lexikografisk ordning. Det första Lyndonordet består endast av alfabetets första tecken (t.ex. strängen "a") och det sista endast av det sista (t.ex. strängen "ö"), så start- och slutpunkterna är givna (från "a" ger algoritmen nästa ("aaa...ab") och från denna får man nästa tills man kommer till "ö"). Om det erhållna Lyndonordets längd delar strängens längd n så läggs den till till den de Bruijn-sekvens man bygger (sålunda "a"&"aaa...ab"&...&"äööö...ö"&"ö").

de Bruijn-torus

En de Bruijn-torus som innehåller alla binära 2×2-matriser. Matrisen med fyra vita bildas exempelvis av de fyra "hörnen".

En de Bruijn-torus är en toroidal array med egenskapen att varje k-när m × n-matris förekommer exakt en gång. (Arrayen behöver inte uttryckas toroidalt utan kan skrivas som en tvådimensionell m × n-matris.) Om n är ett så har vi en de Bruijn-sekvens, och om m=n och jämnt kan man också skapa en torus, annars är det en öppen fråga om de går att tillverka. Den minsta är (4,4;2,2)₂ eller B₂ som är 4x4 stor och som innehåller alla binära 2×2-matriser (den enda möjliga konfigurationen, bortsett från symmetrioperationer, är avbildad till höger). Nästa är (256,256;4,4)₂ som är 256×256 stor och innehåller alla binära 4×4-matriser.

Användning

En de Bruijn-sekvens kan användas för att förkorta en brute force-attack på en portkodsliknande sekvens som inte har en avslutningstangent ("enter" eller "klar") utan accepterar de sista n inslagna tecknen. Till exempel skulle alla fyrsiffriga decimala koder kunna matas in med 10000+3=10003 tangenttryckningar i stället för att mata in 10000 fyrsiffriga koder (40000 tangenttryckningar).

Tecknen i en de Bruijn-sekvens skrivna runt ett cirkulärt föremål kan användas för att analysera dettas riktningsvinkel genom att läsa en sekvens om n tecken som är vända mot en bestämd punkt. Graykoder kan användas på ett liknande sätt. En de Bruijn-torus kan användas för en motsvarande tvådimensionell positionsbestämning.

de Bruijn-sekvenser har allmän användning inom experimentell neurovetenskap och psykologi vid undersökning av betydelsen av ordningen av olika stimuli på ett nervsystem, och kan utvecklas specifikt för funktionell magnetresonanstomografi.

En de Bruijn-sekvens kan användas för att snabbt hitta index för minsta eller mest signifikanta siffra i ett ord genom bitvisa operationer.

Referenser

• van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), ”Circuits and trees in oriented linear graphs”, Simon Stevin 28: 203–217, http://alexandria.tue.nl/repository/freearticles/597493.pdf .
• Berstel, Jean; Perrin, Dominique (2007), ”The origins of combinatorics on words”, European Journal of Combinatorics 28 (3): 996–1022, doi:10.1016/j.ejc.2005.07.019, http://www-igm.univ-mlv.fr/~berstel/Articles/2007Origins.pdf .
• de Bruijn, N. G. (1946), ”A combinatorial problem”, Proc. Koninklijke Nederlandse Akademie v. Wetenschappen 49: 758–764, http://www.dwc.knaw.nl/DL/publications/PU00018235.pdf, Indagationes Mathematicae 8: 461–467 .
• de Bruijn, N. G. (1975), Acknowledgement of Priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2ⁿ zeros and ones that show each n-letter word exactly once, T.H.-Report 75-WSK-06, Technological University Eindhoven, http://alexandria.tue.nl/repository/books/252901.pdf . (Innehåller även A. de Rivières problemställning och C. Flye Sainte-Maries lösning som appendix.)
• Fredricksen, Harold; Maiorana, James (1978), ”Necklaces of beads in k colors and k-ary de Bruijn sequences”, Discrete Mathematics 23 (3): 207–210, doi:10.1016/0012-365X(78)90002-X .
• Hurlbert, Glenn; Isaak, Garth (1993), ”On the de Bruijn torus problem”, Journal of Combinatorial Theory, Series A 64 (1): 50–62, doi:10.1016/0097-3165(93)90087-O, arkiverad från ursprungsadressen den 2006-09-05, https://web.archive.org/web/20060905092212/http://math.la.asu.edu/~hurlbert/papers/DBTP.pdf .
• Martin, M. H. (1934), ”A problem in arrangements”, Bulletin of the American Mathematical Society 40 (12): 859–864, doi:10.1090/S0002-9904-1934-05988-3, http://www.ams.org/journals/bull/1934-40-12/S0002-9904-1934-05988-3/S0002-9904-1934-05988-3.pdf .
• Ralston, Anthony (1982), ”de Bruijn sequences—a model example of the interaction of discrete mathematics and computer science”, Mathematics Magazine 55 (3): 131–143, doi:10.2307/2690079 .
• Ruskey, Frank (2003), Combinatorial Generation, kap. 7 (DeBruijn Cycles and Relatives (PDF)), sid. 207 ff.
• Tuliani, Jonathan (2001), ”de Bruijn sequences with efficient decoding algorithms”, Discrete Mathematics 226 (1-3): 313–336, doi:10.1016/S0012-365X(00)00117-5 .
• Van Nooten, B. (1993-03-01). ”Binary numbers in Indian antiquity”. Journal of Indian Philosophy 21 (1): sid. 31–50. doi:10.1007/BF01092744. https://link.springer.com/article/10.1007%2FBF01092744. Läst 6 maj 2010. 

Externa länkar

• Weisstein, Eric W., "de Bruijn Sequence", MathWorld. (engelska)
• "Sloanes A166315 : De lexikografiskt minsta binära de Bruijn sekvenserna", Nätuppslagsverket över heltalsföljder (OEIS) (engelska)
• De Bruijn sequence på Chess Programming Wiki
• CGI-generator
• Applet-generator
• Javascript generator och avkodare. Implementation av J. Tulianis algoritm.