Find the least words that will use all given letters

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 1

While there may be a more ideal solution out there than this, I think it will get you closer. Right now your algorithm is rating words that have "rare" letters as more important than overall coverage for the list of letters. Probably the best way of reducing the number of words you use will be to pick words that contain the most letters you still need.

For example, say you're trying to find the least number of words that, together, contain the following letters:

Letters
--------
a
b
c
d
e
f

Words
--------
ace
bread
fork
whistle
crab
monkey
car
fork
dog
diamond

An easy way to figure out how useful each word is would be to look at each word and calculate which of the desired letters it contains. We can make this using an array of boolean flags for each word.

Words    | a | b | c | d | e | f
---------------------------------
ace      | T | F | T | F | T | F
bread    | T | T | F | T | T | F
fear     | T | F | F | F | T | T
whistle  | F | F | F | F | T | F
crab     | T | T | T | F | F | F
monkey   | F | F | F | F | T | F
car      | T | F | T | F | F | F
fork     | F | F | F | F | F | T
dog      | F | F | F | T | F | F
diamond  | T | F | F | T | F | F
coffee   | F | F | T | F | T | T
---------------------------------
Total    | 6 | 2 | 4 | 3 | 6 | 3

Since we are just starting, we need everything. So lets just give each word a score based on how many letters it has that we still need.

Used Words: 
Letters Remaining: a, b, c, d, e, f

Words    | a | b | c | d | e | f | Score
-----------------------------------------
ace      | T | F | T | F | T | F | 3
bread    | T | T | F | T | T | F | 4
fear     | T | F | F | F | T | T | 3
whistle  | F | F | F | F | T | F | 1
crab     | T | T | T | F | F | F | 3
monkey   | F | F | F | F | T | F | 1
car      | T | F | T | F | F | F | 2
fork     | F | F | F | F | F | T | 1
dog      | F | F | F | T | F | F | 1
diamond  | T | F | F | T | F | F | 2
coffee   | F | F | T | F | T | T | 3

So let's take the one that knocks out the most letters. In this case "bread". Which means the only letters we have left to use are "c, f". Let's give each word a new score based on the letters we need.

Used Words: bread
Letters Remaining: c, f

Words    | a | b | c | d | e | f | Score | Score 2 
--------------------------------------------------
ace      | T | F | T | F | T | F | 3     | 1
bread    | T | T | F | T | T | F | 4     | -
fear     | T | F | F | F | T | T | 1     | 1
whistle  | F | F | F | F | T | F | 1     | 1
crab     | T | T | T | F | F | F | 3     | 0
monkey   | F | F | F | F | T | F | 1     | 1
car      | T | F | T | F | F | F | 2     | 1
fork     | F | F | F | F | F | T | 1     | 1
dog      | F | F | F | T | F | F | 1     | 0
diamond  | T | F | F | T | F | F | 2     | 0
coffee   | F | F | T | F | T | T | 3     | 2

Now we can take "coffee" which has a score of 2 and that uses up all the letters we wanted to use. Obviously this has some flaws. First, your subsequent choices depend on what your first choice was. If you picked a word that got a lot of common letters but didn't hit the rarer ones, you will likely end up with one word that hits a lot of letters and a bunch that only get one or two. This could be solved by weighting the scores such that more rare letters are worth more (kinda like playing Scrabble).

One thing you might have noticed is having to recalculate the score on every pass. And that's going to be a pain. But what if we used some clever computer tricks to make that easier? What if, instead of an array of booleans for each word, we just turned that into a sequence of bits? (Same thing, but easier to work with for this.)

So if we rewrote the table where as bits, it might look like this:

Words    | Bits (a|b|c|d|e|f)
---------------------------------
ace      | 101010
bread    | 110110
fear     | 100011
whistle  | 000010
crab     | 111000
monkey   | 000010
car      | 101000
fork     | 000001
dog      | 000100
diamond  | 100100
coffee   | 001011

Calculating the score now becomes a simple XOR with a mask for the letters you need (at the beginning, 111111 then subsequently 001001) then you just count the true bits. Pretty simple recalculation.

If you want to weight the algorithm, it gets a bit easier to execute but harder to set up. If you took a count of each letter to find the rarest ones (like I did in the first part), you could arrange the bitmask to no longer be in say alphabetical order but in order of rarity (most rare being first). In this case your bitmask would look like (b|d|f|c|a|e). Then comparisons of score are just ordering by the highest integer after applying the mask. (Note this does run into some problems when two letters are tied for rarity. Just be aware it can skew your results. Hopefully there won't be many cases of this in larger lists of words.)

This isn't perfect, but it's a good start.

Answer 2

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. 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.

Answer 3

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