Ik ben (een beetje laat) gegrepen door de Puzzling Adventures van december 2003 van Dennis E. Shasha in Scientific American: verrassende reeksen.
Op deze pagina vind je de resultaten van een sessie van anderhalve dag tijdens mijn internetloze vakantie waarin ik me concentreerde op het oplossen van enkele onderdelen van deze puzzel.
Ik heb me geconcentreerd op de 2-verrassende reeksen. Mijn belangrijkste conclusie is dat ik denk dat de langste reeks voor 26 verschillende symbolen 69 tekens is, en het aantal symbolen dat nodig is voor een verrassende reeks van 100 tekens is 38.
Het eerste wat ik deed was wat Shasha beschrijft op de oplossingswebpagina: ik heb een systematische iterator gemaakt die een object gebruikt voor een verrassende reeks, en een automatisch teruglopend recursief algoritme om de oplossingsruimte te scannen. Een beperking die ik snel heb ingevoerd, is dat de karakters op volgorde worden geïntroduceerd: de verrassende reeks "AAB" verschilt niet van "BBA". Dit scheelt een factor N! in de rekentijd. Maar: zoals vermeld op de webpagina van Shasha over deze puzzel, is deze systematische aanpak zelfs met deze kortere weg nogal tijdrovend. Eigenlijk lijken de prestaties iets slechter dan exponentieel. Op mijn notebook duurde het genereren van alle verrassende reeksen voor korte lengtes:
- for N=3 ~0.01 seconde
- for N=4 0.07 seconde
- for N=5 0.7 seconde
- for N=6 6 seconde
- for N=7 2 minuten
- for N=8 1 uur
Grofweg geëxtrapoleerd, zou N=16 me 8 miljard jaar kosten, en grotere N behoorlijk wat meer dan de leeftijd van het universum.
Zelfs het werken vanaf een willekeurig startpunt voor de langere reeksen tast geen redelijk onafhankelijke gebieden van de oplossingsruimte af, dus implementeerde ik een andere oplosser:
METHODE 2
- Kies een willekeurige, geldige verrassende reeks
- herhaal:
- Haal de laatste 10-15 tekens van het einde af
- Maak een puntmutatie die de reeks niet ongeldig maakt
- Herhaal vanaf daar met behulp van de recursieve procedure.
- Kies de meest succesvolle reeks uit de recursieve set
Dit kost wat tijd bij het uitvoeren van de systematische aanpak ("kleine stappen"), en gebruikt dan de mutatie om ergens anders in de oplossingsruimte ("grote stap") te beginnen. Deze aanpak is erg handig om snel een idee te krijgen van hoe groot oplossingen kunnen zijn voor een bepaald aantal symbolen. Maar het lukte me nog steeds niet om reeksen te krijgen die snel genoeg lang genoeg waren. Dus ging ik voor een derde methode.
METHODE 3
- Kies een willekeurige, niet verrassende reeks van de gewenste lengte.
- Bereken de "error"-score voor de reeks (hoeveel overtredende paren zijn er te vinden).
- herhaal:
- Maak een puntmutatie.
- Gebruik de foutscore van de nieuwe en oude strings en een Metropolis-achtige monte-carlo-benadering om te beslissen of je door wilt gaan met de originele of de nieuwe reeks
Het is duidelijk dat je hiervoor vooraf een doellengte moet kiezen. En: zelfs deze aanpak kan lang (uren) duren om een oplossing te vinden. De oplossingsruimte is ERG ruw.
Toen ik terugkwam van vakantie las ik de pagina van David Joyce die een maximale lengte van 2-verrassende reeksen beschrijft als 3N-1. Maar mijn cijfers wijzen op een striktere limiet: ik heb tests uitgevoerd voor N=3..26, en de langste voorbeelden die ik heb gevonden zijn:
N:L(N) L(N)/N Voorbeeld
3: 7, 2.3333 AABCBAC
4: 10, 2.5000 ABBCADCDBA
5: 12, 2.4000 AABCDCEBAEDB
6: 15, 2.5000 AABCDBEFCFADEBA
7: 18, 2.5714 AABCDBEFGCGEADFBAC
8: 21, 2.6250 ABACDEFGDHECHGBBFEADC
9: 24, 2.6667 ABCDEFGGHIBHEDICFDAEACBG
10: 26, 2.6000 ABCDEFGHIJACEJIICBHBDGADFE
11: 29, 2.6364 ABCDEFAGHEIGCJJHKDKGBIFBAEDCH
12: 31, 2.5833 ABCDEFGHIJKLLEKDAJBGJAIFBDCHCKF
13: 34, 2.6154 ABCDEFGHIJKLMMBHGIDAGJLDCEAEKFCBFI
14: 37, 2.6429 ABCDEFGHIJKLHMKEMLFNGNEADBJIMCCAHDFBK
15: 39, 2.6000 ABCDEFBGHIHGAJEKLCMMNOKFODIJCNGDLAIKBHE
16: 42, 2.6250 ABCDEFGHBIJKLMNKOCGNJMPEPOADDKHJFCLFHIGAEB
17: 45, 2.6470 ABCDEFGFHIJKLLMNOAMPCJQODNBQCIMEPKNGHEGDBAFLJ
18: 47, 2.6111 ABCDEFGHIJKLMENMLDOPKBQGIOQRHNDCCRJAFAPLHDIBFEK
19: 50, 2.6315 ABCDEFGHIJKILMNOOBPQRSKEQSRGNLHJSDFCACLIGDPEBMAKHF
20: 53, 2.6500 ABCDEFGHEIJKLAMINOPQRPKSQTODNCLSLHGMBRFOJTDBGKIHCAPEE
21: 55, 2.6190 ABCDEFGHIJKLKMNLOEHJGPDQRSTUQCASROOBMFBUNITPFELDUGAMK
CH
22: 57, 2.6364 ABCDEFGHIJKLMNMOPLDQRFNSGTPRHBQERTUVVOUCSJAIKFIDBPQOC
HGMLE
23: 61, 2.6522 ABCDEFGHIJKLMNJOPOQRSTFBSUQVKWPMUTTEHVECNPADIWLRKDQAF
JGGBMOHC
24: 63, 2.6250 ABCDEFGHIJKKLBMNOPQREQSTSGPRUDNVJWUHXOCMWIACPFSLVFXIM
AEHKGRDTJB
25: 66, 2.6400 ABCDEFGHIJKLEMNOPQRRSOGTANUJSPVWVCMDLXWQTWHBYRHJLYKFX
IDUCBAPFNMGEO
26: 69, 2.6538 ABCDEFGHIJKLAMNOPQRESTOJSUUQVLNWBXYXDHKRYZFYCGZTPIVOQ
GWKDCRBIHMANEJLS
Dit is enigszins bevooroordeeld, omdat ik mijn computer urenlang heb laten draaien op de reeks met de laagste lengteverhouding, maar het toont wel de trend dat de limietlengte het kleinste gehele getal onder 8/3*N is. De enige opmerkelijke uitzondering is voor N=9 waar een L=24-oplossing daadwerkelijk bestaat. Er kunnen andere exacte 8/3 oplossingen voor grotere N bestaan, maar deze zijn zeer zeldzaam; Ik heb niet veel moeite gedaan om dergelijke oplossingen te vinden.
Ten slotte pakte ik de impliciete uitdaging aan om een verrassende reeks van lengte 100 te vinden. 3/8*100 = 37,5, dus we hebben 38 verschillende symbolen nodig om dit te redden en L(38) zou eigenlijk 101 moeten zijn. Methode 3 heeft een L=100 gevonden oplossing na een aantal uren, en ik ben niet van plan om te proberen een L=101 oplossing te vinden:
N=38 L=100: ABCDEFGHIJKLMNBOPQRSTUVWXWYZaHZbPGEcdefghiARjJehNT
kkDlKjfXldieDVYbUaNQfbICRHOQcFZSKFLCgUEIBGMaXPJTMA
Dit is allemaal in python geprogrammeerd. En als je geinteresseerd bent kun je het downloaden.
Update: Onlangs (juli 2005) nam Dan M. Shaw contact met mij op met zijn resultaten over dezelfde puzzel. Zijn programma's in C# zijn ongeveer 4 ordes van grootte sneller dan mijn python-code, en hij heeft de systematische zoektocht veel langer kunnen voortzetten, tot 12 verschillende symbolen. Voor 12 verschillende symbolen vond hij 1712864 strings met een lengte van 32, de eerste is AABCDEFGHGIJKELFCLKBDJIHBAFDGACE. Met dit resultaat verbeterde hij mijn lengte voor 12 symbolen met 1, en maakte het waarschijnlijker dat de resultaten voor de andere drievoudige symbolen ook verbeterd kunnen worden.
Er is een entry in de On-Line Encyclopedia of Integer Sequences voor de lengtes van 2-verrassende reeksen.