anagrams

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)])


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 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
    mod_words = words
    while mod_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(mod_words.pop(i))
            else:
                # else just remove it
                mod_words.pop(i)

            i += 1
            mod_perm = find_words_in_perm(mod_perm, mod_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)
    word_list = get_word_list(main_word, WORD_LIST)
    words = words_from_perms(perms, 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()