#!/usr/bin/env python# save as perm.py in your current directory# Example of usage:# import perm# dict = perm.load( )# dict.display( 'cats' )import sysclass node: def __init__( self ): self.children = { } self.is_word = False def add( self, word ): """Add a word.""" n = self for letter in word: if letter not in n.children: n.children[ letter ] = node( ) n = n.children[ letter ] n.is_word = True def anagram( self, text ): """Yield all words and remainders for text""" for index in xrange( 0, len( text ) ): letter = text[ index ] if letter in self.children: for match, remainder in self.children[ letter ].anagram( text[ : index ] + text[ index + 1 : ] ): yield text[ index ] + match, remainder if self.children[ letter ].is_word: yield letter, text[ : index ] + text[ index + 1 : ] def do( self, text ): """Form sentences until no remainder or abandon (ugh)""" for result, remainder in self.anagram( text ): if remainder == '': yield result, '' else: for more, left in self.do( remainder ): if left == '': yield result + ' ' + more, left elif more != '': result += ' ' + more remainder = left else: remainder = '' def display( self, text, contains = '' ): """Convenience display mechanism for testing""" matches = { } for result, remainder in self.do( text ): if result not in matches and contains in result: print '"' + result + '"', matches[ result ] = Truedef load( file = '/usr/share/dict/words' ): fd = open( file ) dict = node( ) while True: word = fd.readline( ) if word == '': break word = word.rstrip( ).lower( ) if len( word ) > 1 or word == 'a' or word == 'i': dict.add( word ) return dict