Fyrsiffrig kod - brute force, angående kombinatorik

Jag vet inte så mycket om sånt här, men om man till exempelvis en portkod skall knäcka koden (4-siffrig) utan att veta något om den alls, så kan man (utöver att trycka 0000, 0001, 0002 osv.) kombinera flera koder i en.. Till exempel så kan man skriva 12345 och få med två möjliga kombinationer, dels 1234 och 2345. På så sätt kan man förkorta ner antalet behövda knapptryckningar från 4000 (1000 kombinationer, fyra siffror) till något rätt mycket mindre.. Någon som vet hur den kortaste siffersträngen skulle se ut om man skulle ha med alla 1000 möjliga kombinationer..?

En fyrsiffrig kod innefattar 10 000 olika kombinationer 0000-9999.

Intressant fundering. Här kommer ett exempel för en tvåsiffrig kod så får vi se om ni kan komma på lösningen för 3- respektive 4-siffriga koder.
Följande tabell innehåller alla möjliga kombinationer av två siffror:
0.0 01 02 03 04 05 06 07 08 09
10 1.1 12 13 14 15 16 17 18 19
20 21 2.2 23 24 25 26 27 28 29
30 31 32 3.3 34 35 36 37 38 39
40 41 42 43 4.4 45 46 47 48 49
50 51 52 53 54 5.5 56 57 58 59
60 61 62 63 64 65 6.6 67 68 69
70 71 72 73 74 75 76 7.7 78 79
80 81 82 83 84 85 86 87 8.8 89
90 91 92 93 94 95 96 97 98 9.9

Om man eliminerar alla siffror på varje rad till vänster om punkterna på varje rad fås återstår följande:
0010203040506070809
11213141516171819
223242526272829
3343536373839
44546474849
556575859
6676869
77879
889
9

I en följd blir det den kombination som krävs för att få med alla tvåsiffriga kombinationer om man lägger till en nolla på slutet
(101 tecken):
00102030405060708091121314151617181922324252627282
93343536373839445464748495565758596676869778798899 0

Om man hade slagit 00, 01,02 o.s.v. hade det krävts 161 tecken innan alla kombinationer har prövats eller 200 om portkoden bara läste två tecken åt gången.

Kan ni utifrån ovanstående exempel härleda hur lång den kortaste teckenkombinationen är för en 3- respektive 4-siffrig kod? Någon slags härledning krävs för full poäng. Svaret kommer senare…

Totalt finns det som tidigare skrivits 10000 kombinationer för en 4-siffrig kod.

Jag drar till med en chansning då...
10003? För 4-siffrigt alltså...

Och så ett litet patetiskt försök till förklaring till min (säkert dåliga?) gissning.

Det behövs 4 knapptryckningar för att slå in första kombinationen, därefter 1 tryck för varje ny kombination. Alltså bör antalet knapptryckningar bli (Max antal kombinationer) + (Antal siffror i en kombination-1)
Eller nåt...
EDIT: Förutom för en-siffriga koder då =)

Om någon är intresserad:

Sådana här sviter som innehåller varje tal av längd n exakt en gång har faktiskt ett eget namn: De kallas för de Bruijn-sviter efter en holländsk matematiker som studerade dem på 40-talet. De mest välstuderade sviterna är de binära de Bruijn-sviterna som bara innehåller nollor och ettor. Ett exempel på en sådan svit är 00010111(00), som innehåller alla binära tal av längd tre precis en gång:

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

Vad de Bruijn gjorde var att han beräknade antalet de Bruijn-sviter. I det binära fallet är antalet 2^(2^(n-1)), där n är längden på de tal som vi vill lista.

Exempelvis finns det 2^(2^(4-1)) = 2^8 = 256 de Bruijn-sviter som innehåller alla binära tal av längd fyra precis en gång (ett exempel är 0000111101011001(000)). Den med gott om tid kan ju roa sig med att försöka hitta alla 256. Eftersom en given svit kan "roteras" på 16 olika sätt räcker det att hitta de 256/16 = 16 sviter som börjar med fyra nollor, så det behöver inte ta hela natten.

Binära De Bruijn-sviter dyker upp i kryptologin i samband med linjära skiftregister (Linear Feedback Shift Registers (LFSR) på fackspråk).

Med k istället för 2 (exempelvis k = 10 om vi vill räkna med vanliga decimaltal) är formeln

(k!)^(k^(n-1)).

(k! = 1*2*3* ... *k, så 10! = 1*2*3*4*...*10 = 3628800.) I det diskuterade fallet med tal mellan 0000 och 9999 har vi n = 4 och k = 10, vilket ger (10!)^(10^3), dvs ungefär 10^6560.

Vill ni mot förmodan veta mer om de Bruijn-sviter finns det en hel del information på nätet; sök på "de bruijn sequences" eller "debruijn sequences"

bra och djevligt intressant inlägg Nulle...