anagrams.py

__author__ = '@goldhand'

import itertools
import os
import sys


_root = os.path.dirname(os.path.abspath(__file__))
_lib = os.path.join(_root, 'lib')

WORD_LIST = open(_lib + '/word_list_full.txt', 'r').readlines()


def get_perms(word):
    # returns all possible permutations of a word, removes redundancies in case of words like 'ally'
    # return set([''.join(perm) for perm in itertools.permutations(word)])
    return list(set([''.join(perm) for perm in itertools.permutations(word)]))


def get_word_list(main_word, word_list):
    # strip 'r\n' off of word because they are line separated and this is way faster than:
    # return [word[:-2] for word in word_list]
    return [word[:-2] for word in word_list if len(word) < len(main_word)]


def get_part_word_list(word_list, i):
    return word_list[(i*1000-1000):(i*1000)]


def get_part_perms(perms, i):
    return perms[(i*1000-1000):(i*1000)]


def words_from_perms(perms, word_list):
    # returns all anagrams of a list of permutations, removes redundancies
    words = []
    for word in word_list:
        for perm in perms:
            if word in perm:
                words.append(word)
    return list(set(words))


def make_mod_perm(perm):
    # creates a permutation object to work with
    return {
        'permutation': str(perm),
        'mod_permutation': str(perm),
        'words': []
    }


def find_words_in_perm(mod_perm, words):
    # finds all anagrams in permutation object
    i = 0
    while words:
        # Use a while loop instead of just the for loop to handle redundancy
        for word in words:
            if word in mod_perm['mod_permutation'][:]:
                # if the word is in the permutation:
                # remove it from the 'mod_permutation' and mod_words; add it to 'words'
                mod_perm['mod_permutation'] = ''.join(mod_perm['mod_permutation'].split(word))
                mod_perm['words'].append(words.pop(i))
            else:
                # else just remove it
                words.pop(i)

            i += 1
            mod_perm = find_words_in_perm(mod_perm, words)
    return mod_perm


def find_max_words_in_perms(perms, words):
    word_sets = []
    for perm in perms:
        # get list of perms; append the permutation objects with anagrams to word_sets
        mod_perm = make_mod_perm(perm)
        word_sets.append(find_words_in_perm(mod_perm, words[:]))
        # sort word sets by the length of the permutation objects 'words' len
    return sorted(word_sets, key=lambda x: len(word_sets[word_sets.index(x)]['words']), reverse=True)


def find_2_words_in_perms(perms_words):
    # find a permutation object with 2 words
    for perm in perms_words:
        if len(perm['words']) == 2:
            return perm


def main():
    main_word = str(sys.argv[1])
    perms = get_perms(main_word)
    print len(perms)
    word_list = get_word_list(main_word, WORD_LIST)
    i = 0
    while i < len(perms)/1000:
        #part_word_list = get_part_word_list(word_list, i)
        part_perm_list = get_part_perms(perms, i)
        i += 1
        #words = words_from_perms(perms, part_word_list)
        words = words_from_perms(part_perm_list, word_list)
        print 'Two Words:'
        if len(words) >= 1:
            perms_words = find_max_words_in_perms(perms, words)
            max_perm = perms_words[0]
            two_words_perm = find_2_words_in_perms(perms_words)
            if two_words_perm:
                #print two_words_perm['permutation']
                print two_words_perm['words']
            else:
                print []
            print 'Max Words:'
            #print max_perm['permutation']
            print max_perm['words']
        else:
            print 'Max Words:'


if __name__ == '__main__':
    main()

File "anagrams.py", line 121, in <module>
  main()
File "anagrams.py", line 105, in main
  perms_words = find_max_words_in_perms(perms, words)
File "anagrams.py", line 80, in find_max_words_in_perms
  return sorted(word_sets, key=lambda x: len(word_sets[word_sets.index(x)]['words']), reverse=True)
File "anagrams.py", line 80, in <lambda>
  return sorted(word_sets, key=lambda x: len(word_sets[word_sets.index(x)]['words']), reverse=True)

File "anagrams.py", line 70, in find_words_in_perm
  mod_perm = find_words_in_perm(mod_perm, mod_words)

File "anagrams.py", line 115, in <module>
  main()
File "anagrams.py", line 96, in main
  words = words_from_perms(perms, part_word_list)
File "anagrams.py", line 33, in words_from_perms
  for perm in perms: