Is it possible to generate Pangram from given word list?

Question

Pangram is a sentence using every letter of the alphabet at least once.

Is it possible to generate shortest Pangram from given word list?

Lets say, I have word list like this

cat monkey temp banana christmas 
fast quick quickest jumping 
white brown black blue
fox xor jump jumps oven over 
now the is was 
lazy laziest crazy
dig dog joker mighty

And Like to generate possible pangrams list like followings

the quick over lazy jumps fox dog brown
brown dog fox jumps lazy over quick the
quick brown fox jumps over the lazy dog

Grammar and word ordering is no need to consider for now (I am going to do it in non-english language)

Any Ideas, algorithms, codes, references, will be greatly appreciated!

PS: This is not a homework

Answer 1

The simplest way to generate all possible pangrams from the word list is probably to generate all possible combinations of words from the list, then for each of them, check whether it's a pangram. To do the check, walk through the string and set a bool to true for each letter that's in the string. At the end, it's a pangram iff the bools have all been set to true.

A more efficient method would probably be to walk through each word, and set up an array of bools (or a set of bits, such as in a 32-bit int) along with the length of the word. You can then find the bits that or'd together produce a value with all 26 bits set, and you have a pangram.

As you're putting a pangram together, you can add bounds-check, so if adding a word would make a potential pangram longer than your current shortest pangram (if any) you stop that check right there. If you start by sorting your words by length, the minute you hit a longer combination, you can quit that whole set of attempts, and go on to the next possibility.

If you want to get even more sophisticated about it, You can start by building the same kind of bit set as above. Then take those, and add together the bits to determine which letters occur in the fewest words. When you start to generate a potential pangram, you know it must include one of those words. E.g. in the list you gave above, "lazy", "laziest" and "crazy" seem to be the only ones that include 'z', so you know immediately that every pangram must include one of those three words. None of those includes a "q", and the only words that do include "q" seem to be "quick", and "quickest", so (again) every pangram must include one of those two (of course I'm going from manual inspection here, so I might have missed a word). So, every possible pangram from that list includes (and might as well start with): (quick|quickest) (lazy|laziest|crazy).

You could also consider preprocessing your word list: any word that's longer than another, but doesn't contain at least one letter missing from the other can be eliminated immediately. As a hypothetical example, if you have "ab" and "abab", you know that "abab" can never result in a shorter pangram than "ab", so you might as well eliminate it from the list immediately.