Can we solve this problem more efficiently than trying all possible combinations

Question

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.

Answer 1

I am going to prove that a special case of this problem is NP-hard and hence we can not aim for a polynomial time algorithm for the general case (unless P=NP).

Assuming each word has length exactly 1. This means each word is only one letter and each sentence is a combination of letters. We are looking now for a set of at most $k$ letter that construct as many sentences as possible. In other words, we are looking for the maximum number of sentences that can be constructed with $k$ letters and hence have union at most $k$. This problem is very similar to the NP-hard minimum $k$-union problem and can also be proven hard using the NP-Hard maximum clique problem (See this question for more information).

Note that heuristics can be used to improve the running time if you are not looking for an optimal algorithm. However, a better greedy heuristic than sorting the words from the largest frequency is looking for sentences with the shortest total lengths and high number of intersections with other strings. In this case however, it would only make sense if your algorithm breaks before trying all possible values.