Python - Efficiently working with large permutated lists
<p>I've written a short <strong>Anagram Solver</strong> script in <strong>Python 2.7</strong>. </p>

<pre><code>#Import Permutations Module
from itertools import permutations as perm

#Defined Functions
def check(x,y):

    #Opens Dictionary File
    with open('wordsEn.txt') as dictionary:

        '''Checks the permutations against all of the dictionary words and appends
        any matching ones to on of the empty lists'''

        for line in dictionary:
            for i in x:
                if i + '\n' == line:
                    y.append(i)

#Empty Lists that will be appended to later
anagram_perms = []
possible_words = []

#Anagram User Input
anagram = list(raw_input("Input scrambled word: ").lower())

#Creates single list items from the permutations, deletes duplicates
for char in perm(anagram):
    anagram_perms.append("".join(char))
    anagram_perms = list(set(anagram_perms))

#Uses the defined function
check(anagram_perms, possible_words)

#Prints the number of perms created, then prints the possible words beneath it
print len(anagram_perms)
print '\n'.join(possible_words)
</code></pre>

<p>It essentially takes a user inputted anagram, generates and places into a list all possible combinations of the letters (using <code>itertools.permutations</code>), deleting any duplicates. It then checks each of these of combinations against a 100000 word dictionary text file, placing any matching words into a list to be printed.</p>

<p>I've run into the issue that if a user inputs a word that is above 6 unique letters in length, the number of permutations generated causes hanging and crashes. 9 letter anagrams would be the typical input, however evidently these will output <strong>362880</strong> ('9!') permutations if all letters are different, which is unfeasible.</p>

<p>I've though about a couple of <strong>potential solutions</strong>:</p>

<ol>
<li>Creating a number of empty lists which can only hold a certain number of appended permuations. Once these lists are 'full', permutations are added to the next one. Each of these lists are then subsequently checked against the text file.</li>
<li>Creating one empty list contained within a loop. Permutations are generated and appened to the list up to a certain workable number, the list is then used to check the text file before emptying itself and appending in the next number of permutations.</li>
<li>Some other method whereby a certain number of permutations are generated, then the process is paused while the currently generated ones are checked against the text file, and resumed and repeated.</li>
</ol>

<p>I'm fairly new to Python development however and don't really know if these would be possible or how I would go about implementing them into my code; and other questions on similar topics haven't really been able to help.</p>

<p>If anyone would like to see my code so far I'd be happy to condense it down and post it, but for the sake of not making this question any longer I'll leave it out unless it's requested. <strong>(Updated Above)</strong></p>

<p>Thanks!</p>

<p>It think the best solution may be to not use permutations. It's much more likely than not that most generated permutations are not a word - so it's a waste to generate them all.</p>

<p>You can consider pre-processing this dictionary to a dictionary of sorted letters to list of words that those letters consist of. Then, your anagram solver will be a simple lookup in a dictionary after sorting the input. </p>

<p>First, create the dictionary from your word list and save to a file:</p>

<pre><code>from collections import defaultdict
import json

word_list = ['tab', 'bat', 'cat', 'rat', ...]  # 100k words
word_dict = defaultdict(list)
for word in word_list:
    word_dict[''.join(sorted(word))].append(word)
with open('word_dict.json') as f:
    f.write(json.dumps(dict(word_dict)))
</code></pre>

<p>Then, when running your anagram code, load the dictionary and use it to look up the sorted input:</p>

<pre><code>import json

empty_list = []
with open('word_dict.json', 'r') as f:
    word_dict = json.loads(f.read())

while True:
    anagram = raw_input('Enter in an anagram: ')
    sorted_anagram = ''.join(sorted(anagram))
    print word_dict.get(sorted_anagram, empty_list)
</code></pre>

python python-2.7 permutation itertools anagram