In a set of sentences, how could I determine the fewest sentences that contains all characters?

Question

So, for the sake of simplicity, I am going to use English characters for this example. Let's say I have a set of strings of characters in English ranked by difficulty: Easy, Intermediate, Advanced.

So it would look like:

Easy

1. APQ
2. DL
3. RTE

Intermediate

1. FSMG
2. NDA
3. LOXCW

Advanced

1. GEW
2. ZAY
3. IVK

My question is: How could I go about finding the smallest set of strings that contain all the characters?

In this example, I would not need Easy 2 or Advanced 1 because their characters appear elsewhere in the set and they don't offer any characters not found elsewhere. Is there a type of algorithm best suited for this?

I can't just do a map lookup to see if I have come across a character before because I am looking for the smallest set. Also, I want to make sure, for instance, if I skip Easy 2 that I don't skip Intermediate 2 and Intermediate 3 since that's where I found the D and L that allowed me to skip Easy 2.

As for my real-world application, I have 4135 strings (about 100-200 characters long) split into 6 levels of difficulty, and these strings are sentences in Chinese. These strings have about 4000 unique characters combined. I'm basically looking for which sentences are worth learning and discard the ones that don't offer much/any new characters. Difficulty is mostly irrelevant, but I may run the algorithm within difficulties, then across the board.

Any help would be greatly appreciated.

Answer 1

This is an instance of set cover. It is NP-hard, so there is no efficient algorithm to find the absolute optimal solution. The problem has been studied and there are many techniques out there, which you can find by searching on set cover.

One approach is to use a heuristic to select a subset of strings that might be a little larger than absolutely necessary, but which can be found efficiently. See, e.g., the greedy heuristic and others derived from it.

Another approach is to use a SAT solver or ILP solver to find the optimal solution. This is not guaranteed to terminate within your lifetime; it might, or it might not. Some solvers will let you run for a fixed amount of time and output the best solution found so far.