Keskustelu: Yleinen keskustelu: Merkkijonojen yhdistäminen optimaalisesti

Haluisin tehokkaan algoritmin tähän ongelmaan (tai perustelun ettei kovin tehokasta ole) kun en itse nyt oikein jaksa miettiä.

SIIS Annettuna vaikka 4-merkkisiä merkkijonoja AABB, ABBA, BAAB ja BBAB. Sitten pitäisi keksiä lyhin teksti, joka sisältää nämä kaikki. Esimerkkitapauksessa siis BAABBAB.

Mietin ekaksi, että ongelmaa voisi kuvata verkolla ja ratkaisun saisi minimivirittävänä puuna (no ei tietenkään). Kauppamatkustajan ongelmana ratkaisemista harkitsin myös, mutta sekään ei taida onnistua ainakaan ihan suoraan. Tai en ole ihan varma. Ehkä ongelmaa ei kannata edes lähteä ratkomaan verkolla. Mikään ahne algoritmi kuitenkaan tuskin tuottaa optimaalista tulosta.

Motivaationa vaikka se, että menetelmällä saa pakattua tekstiä jännästi. Jos sattuu olemaan pakattavana teksti AABBABBABAABBBAB, niin sen voi jakaa neljään peräkkäiseen nelimerkkiseen osajonoon. Teksti voidaan sitten esittää tiivistetyssä muodossa tallentamalla pelkkä BAABBAB ja sen indeksit I=[1,2,0,3]. Esitystavalla on lisäksi se kiva ominaisuus, että pakatusta muodosta saa luettua alkuperäisen tekstin merkin esim. kohdasta 10 tosi helposti: I[10/4] + 10%4 = 0 + 2 = 2 eli tulee A koska BAABBAB.

Googlasin. Kyseessä on shortest common superstring, tietenkin eri asia kuin supersequence. StackExchangessa kerrotaan, että ongelma olisi NP-täydellinen. Kirjallisuutta: Approximation Algorithms for the Shortest Common Superstring Problem, Jonathan S. Turner, 1989.

Kuinkas sattuikaan, kyseinen pulma on perjantaina julkistetussa viikkotehtävässä: http://cses.fi/alon/task/84/

Chiman, kaikkien yhdistelmien tuottaminen on kylläkin eri pulma, jonka ratkaisu on De Bruijnin jono. Siitä Deffi jo tietääkin.

Metabolix: Hyvä pointti. Näin tuon saman pulman erikoistapauksena, mutta tosiaan kaikkien yhdistelmien sisältyminen ratkeaa suoremmin.