b'\n_START_ARTICLE_\nDe Bruijn-sekvens\n_START_PARAGRAPH_\nInom kombinatoriken \xc3\xa4r en k-n\xc3\xa4r de Bruijn-sekvens B(k,\xc2\xa0n) av ordningen n en cyklisk sekvens till ett givet alfabet A med storleken k i vilken varje m\xc3\xb6jlig delsekvens av l\xc3\xa4ngden n upptr\xc3\xa4der en och endast en g\xc3\xa5ng som p\xc3\xa5 varandra f\xc3\xb6ljande tecken. Sekvensen \xc3\xa4r uppkallad efter den holl\xc3\xa4ndske matematikern Nicolaas Govert de Bruijn._NEWLINE_Varje B(k,\xc2\xa0n) har l\xc3\xa4ngden k\xe2\x81\xbf._NEWLINE_Det finns  skilda de Bruijn-sekvenser B(k,\xc2\xa0n)._NEWLINE_Enligt de Bruijn sj\xc3\xa4lv bevisades existensen av de Bruijn-sekvenser f\xc3\xb6r alla ordningar med ovanst\xc3\xa5ende egenskaper f\xc3\xb6rst f\xc3\xb6r alfabet med tv\xc3\xa5 bokst\xc3\xa4ver av Camille Flye Sainte-Marie 1894, medan utvidgningen till st\xc3\xb6rre alfabeten \xc3\xa4r ett verk av Tanja van Aardenne-Ehrenfest och honom sj\xc3\xa4lv.\n_START_SECTION_\nHistoria\n_START_PARAGRAPH_\nDet tidigaste k\xc3\xa4nda exemplet p\xc3\xa5 en de Bruijn-sekvens kommer fr\xc3\xa5n sanskritsprosodi. Sedan Pingalas arbeten har varje m\xc3\xb6jligt trestavigt m\xc3\xb6nster av l\xc3\xa5nga och korta vokaler ett namn i form av en konsonant: som "y" f\xc3\xb6r kort-l\xc3\xa5ng-l\xc3\xa5ng och "r" f\xc3\xb6r l\xc3\xa5ng-kort-l\xc3\xa5ng. F\xc3\xb6r att komma ih\xc3\xa5g dessa namn, anv\xc3\xa4nds minnesramsan yam\xc4\x81t\xc4\x81r\xc4\x81jabh\xc4\x81nasalag\xc4\x81m, i vilken varje trestavigt m\xc3\xb6nster inleds av sitt "konsonantnamn": yam\xc4\x81t\xc4\x81 har allts\xc3\xa5 ett kort-l\xc3\xa5ng-l\xc3\xa5ng-m\xc3\xb6nster, r\xc4\x81jabh\xc4\x81 l\xc3\xa5ng-kort-l\xc3\xa5ngt, och s\xc3\xa5 vidare. Denna minnesramsa, som \xc3\xa4r ekvivalent med en de Bruijn-sekvens av bin\xc3\xa4ra tripplar (0111010001 vilket motsvarar 11101000, med till\xc3\xa4gg av f\xc3\xb6rsta och sista tecknet i andra \xc3\xa4nden 0+11101000+1 f\xc3\xb6r att kompensera f\xc3\xb6r att ramsan \xc3\xa4r linj\xc3\xa4r och ej cyklisk), \xc3\xa4r av ok\xc3\xa4nd \xc3\xa5lder men \xc3\xa4r \xc3\xa5tminstone lika gammal som C. P. Browns bok fr\xc3\xa5n 1869 om versm\xc3\xa5tt p\xc3\xa5 sanskrit som n\xc3\xa4mner den._NEWLINE_I ett nummer av den franska pusseltidskriften L\'Interm\xc3\xa9diaire des Math\xc3\xa9maticiens st\xc3\xa4llde A. de Rivi\xc3\xa8re 1894 fr\xc3\xa5gan om det fanns ett s\xc3\xa4tt att arrangera alla  bin\xc3\xa4rsekvenser av l\xc3\xa4ngden n i en cirkul\xc3\xa4r str\xc3\xa4ng med l\xc3\xa4ngden . Problemet l\xc3\xb6stes, tillsammans med r\xc3\xa4kningen av antalet l\xc3\xb6sningar , av C. Flye Sainte-Marie samma \xc3\xa5r. Detta gl\xc3\xb6mdes dock mer eller mindre bort och Martin (1934) bevisade existensen av s\xc3\xa5dana cykler f\xc3\xb6r generella storlekar av alfabet andra \xc3\xa4n tv\xc3\xa5. Slutligen, n\xc3\xa4r K. Posthumus st\xc3\xa4llde antagandet att antalet bin\xc3\xa4ra sekvenser var , bevisade de Bruijn antagandets riktighet 1946, genom vilket problemet blev v\xc3\xa4lk\xc3\xa4nt._NEWLINE_Karl Popper beskriver oberoende dessa bin\xc3\xa4rsekvenser i avsnitt 55 av sin Logik der Forschung (1934) och kallar dem n-Nachwirkungsfreie Alternativen och ger \xc3\xa4ven formeln f\xc3\xb6r deras antal._NEWLINE_De Bruijn skriver att "motsvarande r\xc3\xa4kningsproblem f\xc3\xb6r ett alfabet med \xcf\x83 bokst\xc3\xa4ver verkar f\xc3\xb6rst ha st\xc3\xa4llts och l\xc3\xb6sts 1951" och avser d\xc3\xa5 van Aardenne-Ehrenfest, de Bruijn (1951).\n_START_SECTION_\nKonstruktion\n_START_PARAGRAPH_\nde Bruijn-sekvenser kan konstrueras genom att ta en Hamiltonv\xc3\xa4g p\xc3\xa5 en n-dimensionell de Bruijn-graf \xc3\xb6ver k tecken (eller, likv\xc3\xa4rdigt, en Eulercykel p\xc3\xa5 en (n\xc2\xa0\xe2\x88\x92\xc2\xa01)-dimensionell de Bruijn-graf)._NEWLINE_En alternativ konstruktion kan \xc3\xa5stadkommas genom att konkatenera alla Lyndonord som har en l\xc3\xa4ngd som delar n i lexikografisk ordning. Se artikeln om Lyndonord f\xc3\xb6r en n\xc3\xa4rmare beskrivning._NEWLINE_de Bruijn-sekvenser kan ocks\xc3\xa5 skapas genom att anv\xc3\xa4nda skiftregister_NEWLINE_eller via \xc3\xa4ndliga kroppar.\n_START_SECTION_\nAlgoritm\n_START_PARAGRAPH_\nMan kan bilda en de Bruijn-sekvens genom konkatenering i lexikografisk ordning av alla Lyndonord med en l\xc3\xa4ngd som delar n. Det finns en algoritm som genererar alla Lyndonord med l\xc3\xa4ngder upp till och med n i lexikografisk ordning. Det f\xc3\xb6rsta Lyndonordet best\xc3\xa5r endast av alfabetets f\xc3\xb6rsta tecken (t.ex. str\xc3\xa4ngen "a") och det sista endast av det sista (t.ex. str\xc3\xa4ngen "\xc3\xb6"), s\xc3\xa5 start- och slutpunkterna \xc3\xa4r givna (fr\xc3\xa5n "a" ger algoritmen n\xc3\xa4sta ("aaa...ab") och fr\xc3\xa5n denna f\xc3\xa5r man n\xc3\xa4sta tills man kommer till "\xc3\xb6"). Om det erh\xc3\xa5llna Lyndonordets l\xc3\xa4ngd delar str\xc3\xa4ngens l\xc3\xa4ngd n s\xc3\xa5 l\xc3\xa4ggs den till till den de Bruijn-sekvens man bygger (s\xc3\xa5lunda "a"&"aaa...ab"&...&"\xc3\xa4\xc3\xb6\xc3\xb6\xc3\xb6...\xc3\xb6"&"\xc3\xb6").\n_START_SECTION_\nde Bruijn-torus\n_START_PARAGRAPH_\nEn de Bruijn-torus \xc3\xa4r en toroidal array med egenskapen att varje k-n\xc3\xa4r m\xc2\xa0\xc3\x97\xc2\xa0n-matris f\xc3\xb6rekommer exakt en g\xc3\xa5ng. (Arrayen beh\xc3\xb6ver inte uttryckas toroidalt utan kan skrivas som en tv\xc3\xa5dimensionell m\xc2\xa0\xc3\x97\xc2\xa0n-matris.) Om n \xc3\xa4r ett s\xc3\xa5 har vi en de Bruijn-sekvens, och om m=n och j\xc3\xa4mnt kan man ocks\xc3\xa5 skapa en torus, annars \xc3\xa4r det en \xc3\xb6ppen fr\xc3\xa5ga om de g\xc3\xa5r att tillverka. Den minsta \xc3\xa4r (4,4;2,2)\xe2\x82\x82 eller B\xe2\x82\x82 som \xc3\xa4r 4x4 stor och som inneh\xc3\xa5ller alla bin\xc3\xa4ra 2\xc3\x972-matriser (den enda m\xc3\xb6jliga konfigurationen, bortsett fr\xc3\xa5n symmetrioperationer, \xc3\xa4r avbildad till h\xc3\xb6ger). N\xc3\xa4sta \xc3\xa4r (256,256;4,4)\xe2\x82\x82 som \xc3\xa4r 256\xc3\x97256 stor och inneh\xc3\xa5ller alla bin\xc3\xa4ra 4\xc3\x974-matriser.\n_START_SECTION_\nAnv\xc3\xa4ndning\n_START_PARAGRAPH_\nEn de Bruijn-sekvens kan anv\xc3\xa4ndas f\xc3\xb6r att f\xc3\xb6rkorta en brute force-attack p\xc3\xa5 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\xc3\xa4llet f\xc3\xb6r att mata in 10000 fyrsiffriga koder (40000 tangenttryckningar)._NEWLINE_Tecknen i en de Bruijn-sekvens skrivna runt ett cirkul\xc3\xa4rt f\xc3\xb6rem\xc3\xa5l kan anv\xc3\xa4ndas f\xc3\xb6r att analysera dettas riktningsvinkel genom att l\xc3\xa4sa en sekvens om n tecken som \xc3\xa4r v\xc3\xa4nda mot en best\xc3\xa4md punkt. Graykoder kan anv\xc3\xa4ndas p\xc3\xa5 ett liknande s\xc3\xa4tt. En de Bruijn-torus kan anv\xc3\xa4ndas f\xc3\xb6r en motsvarande tv\xc3\xa5dimensionell positionsbest\xc3\xa4mning._NEWLINE_de Bruijn-sekvenser har allm\xc3\xa4n anv\xc3\xa4ndning inom experimentell neurovetenskap och psykologi vid unders\xc3\xb6kning av betydelsen av ordningen av olika stimuli p\xc3\xa5 ett nervsystem, och kan utvecklas specifikt f\xc3\xb6r funktionell magnetresonanstomografi._NEWLINE_En de Bruijn-sekvens kan anv\xc3\xa4ndas f\xc3\xb6r att snabbt hitta index f\xc3\xb6r minsta eller mest signifikanta siffra i ett ord genom bitvisa operationer.'