On Sun, Oct 26, 2008 at 10:21 AM, Tolkin, Steve <[EMAIL PROTECTED]> wrote: > The following is just a problem in computer science. It is not directly > related to Perl, or to my work. I am looking for insights in how to > think about this. > > The input: a list of words. > The output: a partitioning of the input list into a longest list of > phrases, such that the phrases are in alphabetical order. (Each phrase > is one of more consecutive words, and a word is a maximum length > sequence of non-space characters.) [...]
> I presume this problem is already known to software engineering. What > is its name? (For example, other problems are solved by "connected > components", or "topological sort", etc.) [...] The algorithm at http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence can be adapted to this problem. You will need small modifications to take into account the fact that "foo bar" is alphabetically before "foo baz" even though the element "foo" is the same both times. Cheers, Ben _______________________________________________ Boston-pm mailing list [email protected] http://mail.pm.org/mailman/listinfo/boston-pm
