Syntactic Confectionery Delight | |
PerlMonks |
Re: minimal superstrings/maximal substringsby The Perlman (Scribe) |
on Aug 21, 2019 at 14:20 UTC ( [id://11104815]=note: print w/replies, xml ) | Need Help?? |
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
In Section
Seekers of Perl Wisdom
|
|