En lidt smartere algoritme end O(n^7)?

[Anders Wegge Keller]

Jeg har en hel masse data, bestående af en kort tekststreng der
starter med GC, efterfulgt af en værdi på 2 til 5 base31[1] kodede
tegn. Hver tekststreng er også fosynet med en dato:

GC3VRBT,02-09-2012
GC3VRCQ,02-09-2012
GC3VRFN,02-09-2012
GC3VRME,02-09-2012
GC3VRN8,02-09-2012

Opgaven er at finde en kombination af tekststrenge, hvor hver af de
31 tegn i base-31 er repræsenteret netop 1 gang, og hvor mindst to af
tekststrengene har samme dato.

Det forholder sig så heldigt at disse strenge lige netop kan klemmes
ind i en 32 bit integer, så det kræver kun en enkelt and at se om en
streng overlapper med en anden, men det tager alligevel sin tid at
lave de her ca. 3^6*10^18/2 sammenligninger jeg skal ud i, for at lave
en exhaustive search af udfaldsrummet.

Den eneste umiddelbare mulighed for at reducere search space er
bundet op på partitioneringen af mine inddata, hvor jeg måske kan
hente en faktor 2000 på O(), ved at lave en udvælgelse på de
strenglængder der sammenlagt giver 31. Det er dog en rimelig
specialiseret løsning, der i høj grad læner sig op af det præcise
inddatasæt jeg har at teste med, og jeg er noget i tvivl om hvorvidt
det vil være en brugbar generel løsning.

Så spørgsmålet er, om der er nogen der kan se en snedigere
algoritme. Jeg kan sagtens leve med en pladskompleksitet i
størrelsesordenen O(n²), hvis det bringer tidskompleksiteten
tilsvarende ned. Med de test jeg indtil videre har lavet på et
reduceret datasæt, regner jeg med at den fulde udsøgning vil tage
noget i retning af en 4-5 dage at køre. Det er lige til den høje side,
selv hvis jeg kaster mig ud i noget parallellisering.


1. 0123456789ABCDEFGHJKMNPQRTVWXYZ

[Bertel Lund Hansen]

Post by Anders Wegge Keller
Opgaven er at finde en kombination af tekststrenge, hvor hver af de
31 tegn i base-31 er repræsenteret netop 1 gang, og hvor mindst to af
tekststrengene har samme dato.

Hvilke krav er der til antallet af elementer i kombinationen?

En slags brute-force-løsning består i at hobe strenge op indtil
alle cifre er repræsenteret og derefter fortsætte til der er to
ens datoer, men jeg har på fornemmelsen at det ikke er
tilfredsstillende.

[Anders Wegge Keller]

Post by Bertel Lund Hansen

Post by Anders Wegge Keller
Opgaven er at finde en kombination af tekststrenge, hvor hver af de
31 tegn i base-31 er repræsenteret netop 1 gang, og hvor mindst to af
tekststrengene har samme dato.

Hvilke krav er der til antallet af elementer i kombinationen?

Ingen, udover at hvert tegn er repræsenteret netop en gang.

Post by Bertel Lund Hansen
En slags brute-force-løsning består i at hobe strenge op indtil alle
cifre er repræsenteret og derefter fortsætte til der er to ens
datoer, men jeg har på fornemmelsen at det ikke er
tilfredsstillende.

Jo, det er sådan set godt nok, men det bliver ikke-trivielt, når
kravet om netop en gang, kommer ind i billedet.

[Bertel Lund Hansen]

Post by Anders Wegge Keller
Jo, det er sådan set godt nok, men det bliver ikke-trivielt, når
kravet om netop en gang, kommer ind i billedet.

Ups, jeg glemte "netop".

[Anders Wegge Keller]

Anders Wegge Keller <***@wegge.dk> writes:

...

Post by Anders Wegge Keller
Så spørgsmålet er, om der er nogen der kan se en snedigere
algoritme. Jeg kan sagtens leve med en pladskompleksitet i
størrelsesordenen O(n²), hvis det bringer tidskompleksiteten
tilsvarende ned.

Lige en opfølgning. Jeg har indset at der for samme dato højst kan
være 30*31 kombinationer af tekststrenge der opfylder det andet
kriterie. Da der højst kan være N/2 grupper af strenge der opfylder
samme krav, kan der spares en O(N) for N>465.

Tricket er at starte med at inddele strengene i grupper efter dato,
og så starte med alle ikke-overlappende kombinationer for hver
dato. Den strategi vil eliminere en hel masse overflødige rekursive
løkker i resten af datasættet, og giver som minimum den O(N) for
passende store værdier af N.