Countdown - word solver

Question

Here is my Countdown word solver.

This code aims to find all possible permutations of any length of a given input (which in the Countdown words game is any random assortment of letters). It then compares each permutation with the dictionary and prints it if it is a valid word. For example the letters "PHAYPC" could yield the following words (not limited to):

• Chap
• Happy
• Hay

I've used the enchant library as my dictionary checker.

import itertools
import enchant

word = input("Please enter the letters or words to scramble: ")
perm_words = itertools.chain.from_iterable(itertools.permutations(word, i) for i in range(3,len(word)))
list_possible = []
list_words_print = []

for item in perm_words:
    list_possible.append("".join(item).lower())

dictionary = enchant.Dict("en_UK")
for word in list_possible:
    if dictionary.check(word):
        if word not in list_words_print: list_words_print.append(word)

print (list(item for item in list_words_print))
exit_key = input("Press any key to exit")

Answer 1

Two suggestions for improvement. First, there's no need to keep track of all those possible words in a list list_possible. You could create and check them on the fly instead, saving memory and a bunch of append calls:

for item in perm_words:
    word = "".join(item).lower()
    if dictionary.check(word):
        if word not in list_words_print: 
            list_words_print.append(word)

EDIT There's a sneaky bug preventing this, as pointed out by OP. Due to perm_words generating the combinations with a length as determined by range(3, len(word)), word is not a variable that should be overwritten in this loop. Or, rename the user input.

---

Second, having a list to keep the dictionary words in is unnecessarily slow. For every new word found, it's being compared to each word in that list. A faster option would be to store them in a set. Sets can't contain duplicates, so you could simply add each word without having to worry if you've seen it before:

found_words = set()
for item in perm_words:
    word = "".join(item).lower()
    if dictionary.check(word):
        found_words.add(word)

Answer 2

Generating all permutations is computationally expensive. For substrings of length n, there would be n! permutations. Note that 9! (which is 362880) likely exceeds the number of words in an English dictionary. Since you say that the input to your program may be of arbitrary length, checking the letter counts of each word in the dictionary would be a better strategy than generating all possible permutations, since it avoids pathological running times for large inputs.