0

My Code

from itertools import permutations

original = str(input('What word would you like to unscramble?: '))

gen = []
for bob in permutations(original):
    gen.append(''.join(bob))



inputFile = open('dic.txt', 'r')
compare = inputFile.read().split('\n')
inputFile.close()

rondo = set(john for john in gen if john in compare)

for magic in rondo:
    print(magic)

I use it to unscramble words by finding all possible permutations of a word and comparing each permutation to a dictionary to find real words, and then returning those real words. However, going over eight letters causes an error as I run out of ram before the program can finish and words with seven or eight letters take a long time to unscramble. I would like to know if there is a way to make my code able to run faster with longer words as well as a way to increase the maximum word length. I'm using Python 3 and am a bit of a beginner if it matters.

TimeWillTell
  • 191
  • 2
  • 11

2 Answers2

2

Instead of appending all of the permutations to a list, you should just iterate over them directly.

set(''.join(john) for john in permutations(original) if ''.join(john) in compare)

or

set(john for john in (''.join(bob) for bob in permutations(original)) if john in compare)

A better way of finding the solution would be to create a signature of the word either by creating a map from letter to count or by sorting the letters. Then you would only need to compare the signature of the scrambled word to the signatures from the word list.

words = {}
for word in compare:
    key = ''.join(sorted(word))
    if key in words:
        words[key].add(word)
    else:
        words[key] = {word}

return words[''.join(sorted(original))]
Strikeskids
  • 3,932
  • 13
  • 27
  • Thank you! I understand what you're saying, but could you possibly please give me a demonstration as I'm not completely sure how to do this. – TimeWillTell Nov 08 '14 at 16:14
  • 1
    You can make a signature by sorting the letters as follows. Scan through your current dictionary file that has one word per line and create a new file that has two words on each line: the original word with the letters sorted alphabetically, followed by the original word. Then to unscramble a word, you just sort it and search for the sorted version in your new file. You may be able to store the new double word list in memory as a Python `dict` with the sorted word as the key and the original version as the value. If not, you can rapidly search through a sorted file using bisection. – PM 2Ring Nov 08 '14 at 16:44
  • This is good, but I would still recommend that the asker of the question understands and make use of generators in the code, as per my answer. – Captain Whippet Nov 09 '14 at 11:40
  • @CaptainWhippet I had also included your answer in mine. However, I didn't separate it out clearly, which is why you probably missed it. – Strikeskids Nov 09 '14 at 16:01
1

You could use a generator instead of list:

gen = ( ''.join(bob) for bob in permutations(original))

This will save you memory usage.

There's a good discussion on the use of generators vs. list comprehensions here: Generator Expressions vs. List Comprehension

There's also another good discussion here: Understanding Generators in Python

Community
  • 1
  • 1
Captain Whippet
  • 2,143
  • 4
  • 25
  • 34