from itertools import combinations, chain
from collections import defaultdict
from Queue import Queue

class tableau:
    def __init__(self,N):
        self.array = [[0 for j in range(N-i)] for i in range(N)]
        self.partition = [0 for i in range(N)]
        self.number_of_row = 0
        self.N = N

    def resize(self,N):
        self.array = [[0 for j in range(N-i)] for i in range(N)]
        self.partition = [0 for i in range(N)]
        self.number_of_row = 0
        self.N = N

    def compute_possible_insert(self):
        answer = [0]
        for i in range(self.number_of_row):
            if self.partition[i] > self.partition[i+1]:
                answer.append(i+1)
        return answer

    def clean_tableau(self,i):
        for j in range(self.number_of_row):
            if self.array[j][self.partition[j]-1] == i:
                self.array[j][self.partition[j]-1] = 0
                self.partition[j] -= 1
                if self.partition[j] == 0:
                    self.number_of_row -= 1
                
    def insert_array(self,i,list):
        for j in list:
            self.array[j][self.partition[j]] = i
            self.partition[j] += 1
            if self.partition[j] == 1:
                    self.number_of_row += 1

    def produce_tuple(self):
        return tuple([tuple([self.array[i][j] for j in range(self.partition[i])]) for i in range(self.number_of_row)])

    def Hecke_row_insert(self,new,row):
        l = self.partition[row]
        for i in range(l):
            if self.array[row][i] > new:
                old = self.array[row][i]
                if (i == 0 or self.array[row][i-1] < new) and (row == 0 or self.array[row-1][i] < new):
                    self.array[row][i] = new
                return old
        if (l == 0 or self.array[row][l-1] < new) and (row == 0 or self.array[row-1][l] < new):
            self.array[row][l] = new
            self.partition[row] += 1
            if l == 0:
                self.number_of_row += 1
        return 0

    def Hecke_insert(self,new):
        new_ele = new
        row = 0
        while new_ele > 0:
            new_ele = self.Hecke_row_insert(new_ele,row)
            row += 1

    def Hecke_insert_word(self,new_word):
        for letter in new_word:
            self.Hecke_insert(letter)

    def copy(self,other):
        if self.N < other.N:
            self.resize(other.N)
        else:
            self.resize(self.N)
        self.number_of_row = other.number_of_row
        for i in range(other.N):
            self.partition[i] = other.partition[i]
            for j in range(self.partition[i]):
                self.array[i][j] = other.array[i][j]

    def copy_from_tuple(self,tup):
        max = 0
        for row in tup:
            for entry in row:
                if entry > max:
                    max = entry
        self.resize(max)
        self.number_of_row = len(tup)
        for i,row in enumerate(tup):
            self.partition[i] = len(row)
            for j,entry in enumerate(row):
                self.array[i][j] = entry

    def anti_standardize(self,list_of_numbers,N):
        self.N = N
        temp_partition = self.partition
        temp_array = self.array
        self.partition = [0 for i in range(N)]
        self.array = [[0 for j in range(N-i)] for i in range(N)]
        for i in range(self.number_of_row):
            self.partition[i] = temp_partition[i]
            for j in range(self.partition[i]):
                self.array[i][j] = list_of_numbers[temp_array[i][j]-1]

    def is_initial(self):
        flag = [False for k in range(N)]
        for i in range(self.number_of_row):
            for j in range(self.partition[i]):
                flag[self.array[i][j]-1] = True
        for entry in flag:
            if not entry:
                return False
        return True

    def row_word(self):
        answer = []
        for row in reversed(self.array):
            for entry in row:
                if entry != 0:
                    answer.append(entry)
        return tuple(answer)
        

class iterator:
    def __init__(self,N):
        self.range = [[[],[0]]] + [[] for i in range(N-1)]
        self.count = [0 for i in range(N)]
        self.length = [2] + [0 for i in range(N-1)]
        self.tableau = tableau(N)
        self.N = N

    def increase(self,i):
        if i == -1:
            return True
        self.tableau.clean_tableau(i+1)
        if self.count[i] == self.length[i]:
            if(self.increase(i-1)):
                return True
        self.count[i] += 1
        self.tableau.insert_array(i+1,self.range[i][self.count[i]-1])
        if (i < self.N-1):
            self.count[i+1] = 0
            possible_insert = self.tableau.compute_possible_insert()
            self.range[i+1] = list(chain(*[combinations(possible_insert, k) for k in range(len(possible_insert)+1)]))
            self.length[i+1] = 2 ** len(possible_insert)
        return False

class directed_graph:
    def __init__(self):
        self.list_of_vertices = defaultdict(dict)

    def new_edge(self,start,end,color):
        self.list_of_vertices[start][color] = end

    def get_edges(self,start,color):
        return self.list_of_vertices[start][color]

    def Hecke_insert(self,start,word):
        v = start
        for letter in word:
            v = self.get_edges(v,letter)
        return v

class set_partition:
    def __init__(self,list_of_tableaux):
        self.forward_dict = dict()
        self.backward_dict = defaultdict(list)
        for T in list_of_tableaux:
            self.forward_dict[T] = T
            self.backward_dict[T].append(T)

    def merge_sets(self,first,second):
        first = self.forward_dict[first]
        second = self.forward_dict[second]
        if first == second:
            return False
        else:
            for T in self.backward_dict[second]:
                self.forward_dict[T] = first
            self.backward_dict[first].extend(self.backward_dict[second])
            self.backward_dict[second] = []
            return True

def classification(N):
    
    list_of_K_equivalent_words = []
    for i in range(1,N+1):
        list_of_K_equivalent_words.append([(i,),(i,i)])
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            list_of_K_equivalent_words.append([(i,j,i),(j,i,j)])
    for i in range(1,N+1):
        for j in range(i+1,N+1):
            for k in range(j+1,N+1):
                list_of_K_equivalent_words.append([(i,k,j),(k,i,j)])
                list_of_K_equivalent_words.append([(j,i,k),(j,k,i)])

    Hecke_tableau = tableau(N)
    iterate = iterator(N)
    list_of_tableaux = []

    graph = directed_graph()
    
    while iterate.increase(N-1) == False:
        new_tableau = iterate.tableau.produce_tuple()
        list_of_tableaux.append(new_tableau)
        for i in range(1,N+1):
            Hecke_tableau.copy(iterate.tableau)
            Hecke_tableau.Hecke_insert_word((i,))
            graph.new_edge(new_tableau,Hecke_tableau.produce_tuple(),i)

    partition_of_tableaux = set_partition(list_of_tableaux)

    new_pairs = Queue()

    for T in list_of_tableaux:
        for group in list_of_K_equivalent_words:
            created_tableau = [graph.Hecke_insert(T,word) for word in group]
            if partition_of_tableaux.merge_sets(created_tableau[0],created_tableau[1]):
                new_pairs.put(tuple(created_tableau))
    
    while not new_pairs.empty():
        pair = new_pairs.get()
        for i in range(1,N+1):
            new_tableaux = [graph.get_edges(T,i) for T in pair]
            if partition_of_tableaux.merge_sets(new_tableaux[0],new_tableaux[1]):
                new_pairs.put(tuple(new_tableaux))

    list_of_classes = []
    number_of_tableaux = 0
    for key,value in partition_of_tableaux.backward_dict.iteritems():
        if len(value) > 0:
            Hecke_tableau.copy_from_tuple(value[0])
            if (Hecke_tableau).is_initial():
                temp_list = []
                for tup in value:
                    Hecke_tableau.copy_from_tuple(tup)
                    temp_list.append(Hecke_tableau.row_word())
                list_of_classes.append(temp_list)
                number_of_tableaux += len(value)

    number_of_classes = len(list_of_classes)

    list_of_classes.sort(key = lambda x : len(x))        
        
    number_of_URT = 0
    while number_of_URT < number_of_classes and len(list_of_classes[number_of_URT]) == 1:
        number_of_URT += 1

    list_of_URT = [list_of_classes[i][0] for i in range(number_of_URT)]
    list_of_non_URT = list_of_classes[number_of_URT:]

    print ""
    print "n = " + str(N)
    print "Number of Tableaux : " + str(number_of_tableaux)
    print "Number of K-Knuth Equivalence Classes : " + str(number_of_classes)
    print "Number of URTs : " + str(number_of_URT)

    flag = True
    while flag:
        print ""
        letter = str(raw_input("Want list of classes? Enter Y or N : "))
        if letter == "Y":
            flag = False
            want_list = True
        elif letter == "N":
            flag = False
            want_list = False
    if want_list:
        file_name = "list_of_classes_" + str(N) + ".txt"
        f = open(file_name, "w")
        f.write("Number of Tableaux = " + str(number_of_tableaux) + "\n")
        f.write("Number of K-Knuth Classes = " + str(number_of_classes) + "\n")
        f.write("Number of URTs = " + str(number_of_URT) + "\n\n")
        f.write("List of non-URTs\n")
        f.write("----------------\n")
        for K_class in list_of_non_URT:
            f.write(str(K_class) + "\n")
        f.write("\n")
        f.write("List of URTs\n")
        f.write("------------\n")
        for URT in list_of_URT:
            f.write(str(URT) + "\n")
        f.close()
        print ""
        print "The list has been outputted to \"" + file_name + "\"."

print "This program computes K-Knuth equivalence data for INITIAL tableaux on [n]."
to_continue = True
while to_continue:
    print ""
    N = int(raw_input("Enter n : "))
    classification(N)
    flag = True
    while flag:
        print ""
        letter = str(raw_input("Continue? Enter Y or N : "))
        if letter == "Y":
            flag = False
        elif letter == "N":
            flag = False
            to_continue = False