Beefy Boxes and Bandwidth Generously Provided by pair Networks
laziness, impatience, and hubris

Re: minimal superstrings/maximal substrings

by The Perlman (Beadle)
on Aug 21, 2019 at 14:20 UTC ( #11104815=note: print w/replies, xml ) Need Help??

in reply to minimal superstrings/maximal substrings

On a side note, the mathematical construct you are describing is known as a "poset" = partially ordered set

The best algorithm depends on your data's size, because a complex algorithm doesn't pay off when only being some seconds faster.

My take on it is to first sort and partition your words in subsets of same length, because every "cover word" must have more letters.

Start by putting all words of the first partition into @uncovered and test them against all words of the next partition.

For each match you'll store into a hash $cover{$smaller}=$bigger and delete $smaller from @uncovered.

Then you'll push the @current_partition to the remaining words in @uncovered and repeat with the next partition.

This is a generic algorithm, your case with 9 up and 8 down can be easily adopted.

- Ron
  • Comment on Re: minimal superstrings/maximal substrings

Log In?

What's my password?
Create A New User
Node Status?
node history
Node Type: note [id://11104815]
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others perusing the Monastery: (6)
As of 2020-09-20 18:16 GMT
Find Nodes?
    Voting Booth?
    If at first I donít succeed, I Ö

    Results (122 votes). Check out past polls.