Beefy Boxes and Bandwidth Generously Provided by pair Networks
Syntactic Confectionery Delight
 
PerlMonks  

Re: minimal superstrings/maximal substrings

by The Perlman (Scribe)
on Aug 21, 2019 at 14:20 UTC ( [id://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

Log In?
Username:
Password:

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

How do I use this?Last hourOther CB clients
Other Users?
Others avoiding work at the Monastery: (4)
As of 2024-03-28 22:40 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?

    No recent polls found