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