Question: With a list of thousands of words and a small list of letters I am trying to find the least amount of words to make use of all given letters, assuming my dictionary of words covers all letters. 

The first step is obviously to remove all words with none of the letters. Then I approached this by calculating the relative rareness of each letter for the remaining words, and sort words by combined relative rarity of the letters they contain relative to their length. So this would put words with relatively rare letters first, assuming it will be increasingly easy to satisfy the remaining, more common letters. After picking the best word with the most "coverage" of letters, I remove those from the list of letters, then loop to recalculate the words rareness for the remaining letters until all letters are satisfied.

This certainly works, but sometimes I get odd results that show how this is not ideal. For example a 5 letter requirement would still find a single best match covering all letters, but adding a 6th letter, all of a sudden I get 4 words returned, because of the sequence of returned words and rareness shifts in an unfavorable way.

What strategy could I use to improve this algorithm? Also I currently iterate over all words several times per loop, counting rareness etc, which gets increasingly expensive with a vast dictionary. Any suggestions welcome :)

Answer: 
If you throw out all the uninteresting letters and words, then reduce each word to the subset of interesting letters contained, you have a [Set cover problem](https://en.wikipedia.org/wiki/Set_cover_problem). This is NP-complete. If you don't want to do an exhaustive search, the best you can do is repeatedly take the word that contains the largest number of unused letters.
I would pre-process each word in the dictionary to map the word to its list of unique letters. Then just look for the map entry with your desired letters.

In a perl one-liner:

```
perl -MList::Util=uniq -slne '
    ($word = $_) =~ s/\W//g;     # remove punctuation, etc
    $key = join "", uniq sort split //, lc $word; 
    push @{$map{$key}}, $_;
  } END {
    print join "\n", @{$map{$letters}};
' -- -letters=aehilpst  /usr/share/dict/words

```

```
philatelist
philatelist's
philatelists
shapeliest
slaphappiest
splashiest

```