Beefy Boxes and Bandwidth Generously Provided by pair Networks
"be consistent"
 
PerlMonks  

Re: Divide a list of string into substrings

by BillKSmith (Monsignor)
on Jun 20, 2020 at 22:39 UTC ( #11118297=note: print w/replies, xml ) Need Help??


in reply to Divide a list of string into substrings

I think that I understand your requirements.

Given a set of strings.

  • Split each string into a list of substrings of at least three character each
  • From the set of all possible decompositions, select the one with the lowest score

Scoring a decomposition

  • Form the set of all the substrings (Keep only one of each duplicated substrings)
  • Sum the lengths of all the substrings in that set.
  • The score is that sum plus twice the number of substrings in the set.

    • I suspect that execution time of any solution would be exponential in the total number of characters.

Bill
  • Comment on Re: Divide a list of string into substrings

Replies are listed 'Best First'.
Re^2: Divide a list of string into substrings
by Anonymous Monk on Jun 21, 2020 at 09:18 UTC

    Hi Bill

    You understood the problem. Your way guarantees the best result, but as you wrote for a longer list you will get an issue with the runtime.

    What I am looking for is: Some ideas to do the job, to get a good result (low score) in a reasonable runtime even for longer lists and strings. Knowing that this fast approach might not give the optimal solution (lowest score).

[reply]

In Section Seekers of Perl Wisdom

Log In?
Username:
Password:

What's my password?
Create A New User
Domain Nodelet?

www.com | www.net | www.org
Node Status?
node history
Node Type: note [id://11118297]
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others chanting in the Monastery: (4)
As of 2021-10-25 05:33 GMT
Sections?
Information?
Find Nodes?
Leftovers?
    Voting Booth?
    My first memorable Perl project was:







    Results (89 votes). Check out past polls.
    Notices?