Here is the context of the problem I am struggling with.
I have a set of strings, for example:
"my name is john", "i like cheese", "what is your name", "the cheese is in the kitchen", "john likes cheese"
Let $S$ be union of all words appearing in the previous strings.
The problem seeks an optimal combination of words, that construct the maximum number of strings from the initial set, under the following conditions :
- Words are separated by a comma.
- The sum of the lengths of selected words is bounded by a constant number (say 25).
- A sting can be rebuilt only if all words occurring in this string are contained in the selected combination.
For example, the combination
john,cheese,like,likes,i uses 24 characters and allows to rebuild both
"i like cheese" and
"john likes cheese".
Here is what I have tried to implement.
First, I sort every single word by the number of strings it's contained in. In this example:
is (3) cheese (3) john (2) name (2) my (1) i (1) like (1) what (1) your (1) ...
So I'm now using this array:
[is, cheese, john, name, my, i, like, ...], let us call it
And here is the idea of the algorithm I amm using.
First, I initialize another array of strings containin of all the strings g the first word from
initial_array, let's call it
Then, while the total length of all the strings of
new_array plus the commas does not exceed the limit of 25 chars, I append them:
[is,cheese] (9) [is,cheese,john] (14) [is,cheese,john,name] (19) [is,cheese,john,name,my] (22) [is,cheese,john,name,my,i] (24) --> best potential combination so far, can rebuild 1 string: "my name is john" [is,cheese,john,name,my,i,like] (29) --> up to 25 chars
When I reach a length up to 25 chars, I try to replace the last element of
new_array by the following of
[is,cheese,john,name,my,i,what] (29) --> up to 25 chars [is,cheese,john,name,my,i,your] (29) --> up to 25 chars ...
And when I reach the last word of
initial_array, I remove it from
new_array and replace the previous one by the next one of
// if the last word of initial_array is "likes" [is,cheese,john,name,my,i,likes] --> we reached the last word [is,cheese,john,name,my,like] [is,cheese,john,name,my,like,what] etc...
If this solution allows me to try all the possible combinations without repetitions, the running time increases exponentially as words are being added to the
initial_array, and quickly becomes unusable. So I am looking for a better idea to improve this algorithm.
Thank you for your help.