« Thompas Blog | Main | Mer om myntsingling »
oktober 08, 2004
de Bruijn-sekvenser (portkodsproblemet)
Tänk att du har glömt din portkod och ska försöka testa alla möjligheter men vill knappa in så få siffror som möjligt. Hur ska du gå tillväga? Förutsättningen är att portkoden har fyra siffror (0-9) och att man inte behöver trycka "Enter" eller liknande efter varje sekvens som testas, dvs det är bara att knappa på tills rätt sekvens slagits in.
För något år sedan var jag intresserad av just detta problem och skrev två program för att få fram denna typ av sekvenser som alltså kallas för de Bruijn-sekvenser: Ett CGI-program som har en rätt kraftig restriktion av hur stora sekvenserna kan vara, och en Java-applet utan några sådana begränsningar. Här visas en lösning på ovanstående problem.
Stefan Geens skrev idag en lång och fascinerande exposé över detta problem i The de Bruijn code, där han bl.a. var vänlig nog att länka till ett av dessa program. Han förklarar naturligtvis allting mer och bättre.
För fullständighetens skull refereras åter till källorna:
Mathworld: de Bruijn sequence
The (Combinatorial) Object Server: Information on necklaces, unlabelled necklaces, Lyndon words, De Bruijn sequences där jag fick tag i den algoritmen som används i programmen.
Posted by hakank at oktober 8, 2004 10:15 EM Posted to Matematik
Comments
Roligt. Jag missade förra omgången om de Bruijn, men har alltid känt på mig att det borde finnas nåt sånt, men inte vetat i vilken ände jag skulle börja räkna...
Mitt intresse för talserier har annars inskränkt sig till varför 1/7 blir just 0,142857142857..., där varje två-grupp av decimaler ser ut att vara dubbelt så stor som den förra, fast bara nästan, och att det fungerar trots att det inte ser ut som det vid första anblicken...
Posted by: Simon at oktober 10, 2004 11:48 FM