De Bruijn-sekvens
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/ba/De_Bruijn_sequence.svg/250px-De_Bruijn_sequence.svg.png)
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.
Varje B(k, n) har längden kn.
Det finns skilda de Bruijn-sekvenser B(k, n).
Enligt de Bruijn själv[1] 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,[2] 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.[3][4] För att komma ihåg dessa namn, används minnesramsan yamātārājabhānasalagām[5], 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.[6] 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.[6][7][8][9]
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 binärsekvenser av längden n i en cirkulär sträng med längden . Problemet löstes, tillsammans med räkningen av antalet lösningar , 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 , bevisade de Bruijn antagandets riktighet 1946, genom vilket problemet blev välkänt.[1]
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.[10]
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).[1]
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).[11]
En alternativ konstruktion kan åstadkommas genom att konkatenera alla Lyndonord som har en längd som delar n i lexikografisk ordning.[12] Se artikeln om Lyndonord för en närmare beskrivning.
de Bruijn-sekvenser kan också skapas genom att använda skiftregister[13] eller via ändliga kroppar.[14]
Exempel
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/38/De_bruijn_graph-for_binary_sequence_of_order_4.svg/250px-De_bruijn_graph-for_binary_sequence_of_order_4.svg.png)
Mål: Att konstruera en B(2, 4) de Bruijn-sekvens med längden 24 = 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
![](http://upload.wikimedia.org/wikipedia/commons/thumb/6/65/2-2-4-4-de-Bruijn-torus.svg/150px-2-2-4-4-de-Bruijn-torus.svg.png)
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)2 eller B2 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)2 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,[15] och kan utvecklas specifikt för funktionell magnetresonanstomografi.[16]
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.[17]
Noter
- ^ [a b c] De Bruijn (1975).
- ^ Flye Sainte-Marie, C. (1894), ”Solution to question nr. 48”, L'intermédiaire des Mathématiciens 1: 107–110
- ^ van Nooten (1993)
- ^ Subhash Kak, 2000, Indian binary numbers and the Kațapayādi notation, Annals of the Bhandarkar Oriental Research Institute, vol. 81, 2000, sid. 269-272.
- ^ Skrivs egentligen yamātārājabhānasalagam, men gam är också en lång stavelse, och för tydlighets skull skrivs den här gām.
- ^ [a b] Subhash Kak,2000, Yamātārājabhānasalagāṃ an interesting combinatoric sūtra Arkiverad 29 oktober 2014 hämtat från the Wayback Machine., Indian Journal of History of Science, 35.2 (2000), 123-127.
- ^ Rachel W. Hall. Math for poets and drummers Arkiverad 12 februari 2012 hämtat från the Wayback Machine.. Math Horizons 15 (2008) 10-11.
- ^ Donald Ervin Knuth (2006). The Art of Computer Programming, Fascicle 4: Generating All Trees -- History of Combinatorial Generation. Addison-Wesley. Sid. 50. ISBN 978-0-321-33570-8. http://books.google.com/?id=56LNfE2QGtYC&pg=PA50&dq=Pingala
- ^ Stein, Sherman K. (1963), ”Yamátárájabhánasalagám”, The Man-made Universe: An Introduction to the Spirit of Mathematics, s. 110–118 . Reprinted in Wardhaugh, Benjamin, ed. (2012), A Wealth of Numbers: An Anthology of 500 Years of Popular Mathematics Writing, Princeton Univ. Press, pp. 139–144.
- ^ Karl Popper (1935) (på tyska). Logik der Forschung. Routledge. Sid. 108. ISBN 978-0-415-27843-0. http://monoskop.org/images/e/ea/Popper_Karl_Logik_der_Forschung_Zur_Erkenntnistheorie_der_Modernen_Naturwissens_chaft_1935.pdf. Läst 29 oktober 2014 Arkiverad 9 november 2014 hämtat från the Wayback Machine. ”Arkiverade kopian”. Arkiverad från originalet den 9 november 2014. https://web.archive.org/web/20141109094011/http://monoskop.org/images/e/ea/Popper_Karl_Logik_der_Forschung_Zur_Erkenntnistheorie_der_Modernen_Naturwissens_chaft_1935.pdf. Läst 29 oktober 2014.
- ^ Klein, Andreas (2013), Stream Ciphers, Springer, s. 59, ISBN 9781447150794, http://books.google.com/books?id=GYpEAAAAQBAJ&pg=PA59 .
- ^ Enligt Berstel & Perrin (2007), beskrevs den sekvens som genereras på detta sätt först av Martin (1934) (strängen skapades med en annan metod), och sambandet mellan den och Lyndonorden observerades av Fredricksen & Maiorana (1978).
- ^ Goresky, Mark; Klapper, Andrew (2012), ”8.2.5 Shift register generation of de Bruijn sequences”, Algebraic Shift Register Sequences, Cambridge University Press, s. 174–175, ISBN 9781107014992, http://books.google.com/books?id=sd9AqHeeHh4C&pg=PA174 .
- ^ 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 . See in particular "the finite field approach", pp. 136–139.
- ^ GK Aguirre, MG Mattar, L Magis-Weinberg. (2011) ”de Bruijn cycles for neural decoding”. Arkiverad från originalet den 4 mars 2016. https://web.archive.org/web/20160304074335/https://cfn.upenn.edu/aguirre/wiki/public%3Ade_bruijn. . NeuroImage 56: 1293–1300
- ^ ”De Bruijn cycle generator”. Arkiverad från originalet den 26 januari 2016. https://web.archive.org/web/20160126133108/https://cfn.upenn.edu/aguirre/wiki/public%3Ade_bruijn_software.
- ^ Anderson, Sean Eron (1997–2009). ”Bit Twiddling Hacks”. Stanford University. http://graphics.stanford.edu/~seander/bithacks.html. Läst 12 februari 2009.
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 2n 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.