Python Anagram Find Method

This Python example finds anagrams within a word list. It uses sorted strings and a dictionary.
Anagrams. Finding anagrams, words made up of letters of other words, is a classic computer programming puzzle. Solutions can be simple, slow, complex or fast.
A simple approach. One way to find one-word anagrams is to sort each word's chars in a word list. Then, in a dictionary, use those sorted strings as keys. Values are the possible words.
Our implementation. Consider this program. It has three methods. In build_dict we load in a file and parse it—we strip lines, sort their characters, and then add them to a dictionary.StripDictionary

Sorted_line: This method alphabetizes the characters in a string. It uses a list comprehension to get a list, then sorts it and joins it.

Sort

Anagram: This method returns a list of anagrams for a word. It sorts again and splits the result string from the dictionary.

Python program that finds anagrams def build_dict(path): # Load in word file and sort each line. alpha = {} f = open(path, "r") for line in f.readlines(): line = line.strip() key = sorted_line(line) # Add each line to a dictionary based on its sorted key. if key in alpha: v = alpha.get(key) + "," + line alpha[key] = v else: alpha[key] = line return alpha def sorted_line(line): # Sort the chars in this line and return a string. chars = [c for c in line] chars.sort() return "".join(chars) def anagram(alpha, line): # Return a list of anagrams from the dictionary. # ... Use a sorted string as the key. key = sorted_line(line) values = alpha.get(key, "NONE") return values.split(",") # Load our dictionary and use it. alpha = build_dict(r"C:\enable1.txt") results = anagram(alpha, "spot") print("Anagrams for [spot]") print(results) Output Anagrams for [spot] ['opts', 'post', 'pots', 'spot', 'stop', 'tops']
Design notes. The values in the dictionary are stored as strings. Each string is separated by commas. This approach is not ideal but may be simpler (and faster) to use.

Tip: For top performance, a directed acyclic graph is used to find anagrams. Matches can be found by a simple tree traversal.

Word list: The word list used in the program is available on the Internet. I recommend a Google search.

In The Art of Computer Programming, a classic text, Donald Knuth finds anagrams. He computes permutations, combinations. These puzzles build great programming skill.
Most programming tasks involve no anagrams. In fact they often involve no algorithms at all. But practicing with these concepts can lead to new ideas, new inventions.
© 2007-2019 Sam Allen. Every person is special and unique. Send bug reports to info@dotnetperls.com.
HomeSearch
Home
Dot Net Perls