Find subsets i strenge.

[Anders Wegge Keller]

Givet tekststrengene "1245", "2356", "1367", "4567" "45" og "67", vil
jeg gerne have fundet det subset der udgør en lukket gruppe i præcis
så mange strenge som gruppens længde, altså her 123.

Der kan være op til 9 tekstrenge, som input, hver med 2 eller flere
af tallene fra et til ni, og hvert tal kan kun optræde en gang i en
streng. Opgaven er altså ikke mere omfattende, end at det kan lade sig
gøre at brute-force den, men jeg vil foretrække at finde en lidt
snedigere algoritme.

[Niels L. Ellegaard]

Post by Anders Wegge Keller
Givet tekststrengene "1245", "2356", "1367", "4567" "45" og "67", vil
jeg gerne have fundet det subset der udgør en lukket gruppe i præcis
så mange strenge som gruppens længde, altså her 123.
Der kan være op til 9 tekstrenge, som input, hver med 2 eller flere
af tallene fra et til ni, og hvert tal kan kun optræde en gang i en
streng. Opgaven er altså ikke mere omfattende, end at det kan lade sig
gøre at brute-force den, men jeg vil foretrække at finde en lidt
snedigere algoritme.

Hvis jeg læser dit indlæg rigtigt, så kan du formulere problemet ved
hjælp af graf teori. Ideen er at du kan tegne en orienteret multigraf,
hvor hver knude svarer til et bogstav, og hvor hver kantfarve svarer
til en af dine tekstrenge. Nu leder du efter en metode til at finde
"regnbuefarvede hamiltonkredse i en orienteret kantfarvet multigraf".

Hvis man søger på google efter "rainbow cycles" og "graph" kan man
finde en del hits, men jeg har ikke kigget dem allesammen igennem.

I princippet kan man sikkert løse problemet ved at lave en kæmpe
hashtabel der indeholder alle regnbuefarvede stier i grafen, men jeg
kan ikke overskue om det er en god ide, og det kræver sikkert et
ekstra check at undersøge om de kredse man finder er hamiltonske.

Niels

[Anders Wegge Keller]

Post by Niels L. Ellegaard

Post by Anders Wegge Keller
Givet tekststrengene "1245", "2356", "1367", "4567" "45" og "67", vil
jeg gerne have fundet det subset der udgør en lukket gruppe i præcis
så mange strenge som gruppens længde, altså her 123.
Der kan være op til 9 tekstrenge, som input, hver med 2 eller flere
af tallene fra et til ni, og hvert tal kan kun optræde en gang i en
streng. Opgaven er altså ikke mere omfattende, end at det kan lade sig
gøre at brute-force den, men jeg vil foretrække at finde en lidt
snedigere algoritme.

Hvis jeg læser dit indlæg rigtigt, så kan du formulere problemet ved
hjælp af graf teori. Ideen er at du kan tegne en orienteret
multigraf, hvor hver knude svarer til et bogstav, og hvor hver
kantfarve svarer til en af dine tekstrenge. Nu leder du efter en
metode til at finde "regnbuefarvede hamiltonkredse i en orienteret
kantfarvet multigraf".

Det tror jeg umiddelbart du har ret i. En af mine overvejelser var
netop at se på det som en graf, men jeg nåede aldrig længere end til
at se på hver streng som en knude, og lave kanter mellem knuder der
indeholdt samme værdi.

Post by Niels L. Ellegaard
Hvis man søger på google efter "rainbow cycles" og "graph" kan man
finde en del hits, men jeg har ikke kigget dem allesammen igennem.

Det lyder interessant, og jeg vil prøve at se på det.

Post by Niels L. Ellegaard
I princippet kan man sikkert løse problemet ved at lave en kæmpe
hashtabel der indeholder alle regnbuefarvede stier i grafen, men jeg
kan ikke overskue om det er en god ide, og det kræver sikkert et
ekstra check at undersøge om de kredse man finder er hamiltonske.

Jeg endte med at se på kompleksiteten indenfor de mulige strenge jeg
har at se på, og endte med at bruteforece det. Jeg har maksimalt 9
strenge, med højst et af cifrene fra 1 til 9, så selvom det er en
kompleksitet på O (2^N * N), er det til at leve med. Specielt når det
kan lade sig gøre at tvinge en streng ned i en enkelt integer.