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.
my,name,is,john,i,like,cheese,what,your,the,in,kitchen,likes
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 initial_array
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 new_array
:
[is]
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 initial_array
:
[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 initial_array
:
// 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.