# This program finds anagrams -- words that are rearrangements of other words,
# such as "abridge" and "brigade".
#
# If you run function main() this will look first for anagrams of length 2
# then length 3, then length 4, and so forth.  If you run main2() it will
# ask you for specific words and give you any anagrams of those words.

def CopyList(L):
    # This returns an identical copy of list L
    value = []
    for a in L:
        value.append(a)
    return value

def ExtendPerm(P, n):
    # Here P is a list of all of the possible arrangements of the numbers
    # 0 through n-1.  This makes a new list of all arrangements of the
    # numbers 0 through n.  The idea here is simple: for each arrangement
    # in P this makes n+1 copies, inserting n into a different spot in each
    # copy.
    answer = []
    for list in P:
        for i in range(0, n+1):
            dummy = CopyList(list)
            dummy.insert(i, n)
            answer.append(dummy)
    return answer

def Rearrange(w, p):
    # Here p is a permutation of the numbers from 0 to n-1, where
    # n is the length of string w.  This makes a new string that
    # arranges the letters of w in the order given by p.  For example,
    # if w is "abc" and p is [1, 0, 2] then this returns "bac".
    new_string = ""
    for i in p:
        new_string += w[i]
    return new_string
                          
def Anagrams(string, perms, Words):
    # Here perms is the set of all possible permutations of the number
    # from 0 to n-1, where n is the length of string.   This finds all
    # possible rearrangements of the string and looks them up in the
    # list Words.  Any that are found are returned in a list.
    A_list = []
    for p in perms:
        w = Rearrange(string, p)
        if (w in Words) and (w != string) and not w in A_list:
            A_list.append(w)        
    return A_list

def PrintAnagrams(w, list):
    # This prints word w; indented beneath w it prints all words in the list.
    print "Anagrams of %s:" %w
    for a in list:
        if a != w:
            print "    %s" %a

    
def main():
    # This version of the program first generates all possible permutations
    # (up to length 9) of the numbers 0, 1, 2, ..., 9.  It then finds all
    # anagrams of length 2, then length 3, and so forth   It runs pretty
    # slowly as the strings get longer -- a string of length n has n!
    # different rearrangemets, each of which needs to be looked up in our
    # dictionary of 68,000 words.

    # The first steip is to make a list of all permuations.  The [0] entry
    # is just [ [0] ], because there is just one permutation of [0].
    # The next entry is [ [0,1], [1,0] ] because there are two permutations
    # of [0,1]:  [0,1] and [1,0].
    # The next entry is [ [2,0,1], [0,2,1], [0,1,2], [2,1,0], [1,2,0], [1,0,2] ]
    # which are the 6 permuations of [0,1,2], and so forth.
    AllPerms = []
    AllPerms.append( [ [0] ] )

    for i in range(1, 9):
        AllPerms.append(ExtendPerm(AllPerms[i-1], i))

    # This next block builds up Words, a list of all words in our dictionary.
    Words = []
    F = open("dict.txt", "r")
    for w in F:
        Words.append(w.strip())

    # Finally, we go into a loop that picks out all words of length 2, all
    # words of length 3, and so forth and generates their anagrams
    RANGE_START = 2
    RANGE_END = 3  #  Note that RANGE_END must be no larger than 9
    for length in range(RANGE_START, 1+RANGE_END):
        for w in Words:
            if len(w) == length:
                A = Anagrams(w, AllPerms[len(w)-1], Words)
                if len(A) > 0:
                    PrintAnagrams(w, A)

def main2():
    # This version of the program, like main(), starts by finding all
    # possible permutation.  This time it then goes into a loop asking
    # the user for specific words and finds all permuations of those
    # words.  For this version all words are translated into lowercase.
    AllPerms = []
    AllPerms.append( [ [0] ] )

    for i in range(1, 9):
        AllPerms.append(ExtendPerm(AllPerms[i-1], i))

    Words = []
    F = open("dict.txt", "r")
    for w in F:
        Words.append(w.strip().lower())

    done = False
    while not done:
        w = raw_input( "Which word would you like anagrams of? " )
        if w == "":
            done = True
        elif len(w) <= 10:
            w = w.lower()
            A = Anagrams(w, AllPerms[len(w)-1], Words)
            if len(A) > 0:
                PrintAnagrams(w, A)
            else:
                print "No anagrams found"
        else:
            print "That words is too long; use words of length no more than 10."
                    
main2()