""" Not AT ALL efficient (but easy to read) implementation of our generation tree. Permutations are represented as set of cycles. They are canonically represented as an ordered list of lists, starting with the minimum element. Ex: [[1, 2], [3]] is the permutation ((1 2)(3)) = 213. Python 3.4. """ from random import randint from itertools import chain import sys k = 2 # Permutation Utils def size(sigma): return sum(len(cycle) for cycle in sigma) def index_element(t,a): return next(((i,j) for i in range(len(t)) for j in range(len(t[i])) if t[i][j] == a), None) def cycleof(sigma, i): x, y = index_element(sigma,i) return sigma[x] def antecedent(sigma,i): x, y = index_element(sigma,i) return sigma[x][y-1] def image(sigma, i): x, y = index_element(sigma,i) return sigma[x][(y+1)%len(sigma[x])] def iterated_images(sigma, i, length): x,y = index_element(sigma,i) return sigma[x][y+1:y+length+1] def normalize(sigma): return sorted((c[m:]+c[:m] for c,m in ((c,c.index(min(c))) for c in sigma if len(c)>0))) # Cycle Manipulations def remove(sigma, i): x, y = index_element(sigma,i) return normalize(chain((c for c in sigma if c != sigma[x]),[sigma[x][:y]+sigma[x][y+1:]])) def insert_inplace(sigma, a, b): index_b = index_element(sigma,b) if index_b: del sigma[index_b[0]][index_b[1]] if a == b: sigma += [[b]] else: i, j = index_element(sigma, a) sigma[i].insert(j+1, b) return sigma def insert(sigma, a, b): return normalize(insert_inplace([c[:] for c in sigma], a, b)) def split(sigma, a, b): sigmaprime = [cycle[:] for cycle in sigma] a_i, a_j = index_element(sigmaprime, a) b_i, b_j = index_element(sigmaprime, b) if a_i == b_i: m, M = min(a_j,b_j), max(a_j,b_j) del sigmaprime[a_i] sigmaprime.append(sigma[a_i][m:M]) sigmaprime.append(sigma[a_i][:m]+sigma[a_i][M:]) return normalize(sigmaprime) def append(sigma, a, b): sigmaprime = [cycle[:] for cycle in sigma] a_i, a_j = index_element(sigmaprime, a) b_i, b_j = index_element(sigmaprime, b) if a_i != b_i: del sigmaprime[a_i] new_b_i, j = index_element(sigmaprime, b) del sigmaprime[new_b_i] sigmaprime.append(sigma[a_i][a_j:]+sigma[a_i][:a_j]+sigma[b_i][b_j:]+sigma[b_i][:b_j]) return normalize(sigmaprime) # K-cycles preserving generation tree def largest_non_kcycles(sigma): return max((max(cycle) for cycle in sigma if len(cycle) != k), default=0) def special_cycle(sigma): return next((cycle for cycle in sigma if len(cycle) < k), []) def minimum_special_cycle(sigma): return min(special_cycle(sigma), default=0) def non_critical_cycles(sigma): cycles = [c for c in sigma if len(c) != k] for i in range(len(cycles)): if len(cycles[i]) == 2*k: if i==len(cycles)-1 and cycles[i][k] == min(cycles[i][k:]): continue if i= k+1: x = p_cyc[k-1] y = p_cyc[k] sigma_1 = insert(sigma, gamma, x) sigma_2 = insert(sigma, gamma, y) remel = p_cyc[k-1:] if non_critics[1:]: remel += [non_critics[1][0]] p_prime = min([x for x in remel if x != p]) p_second = min([x for x in remel if x != p and x != p_prime]) if L(p) == 2*k+1: if x == p_prime and y == p_second: return split(sigma_1, p, p_second) if y == p_prime: return split(sigma_1, p, p_prime) if L(p) != k+1: return insert(sigma, gamma, p_cyc[-1]) if x == p_prime: if y == p_second : return insert(sigma_1, p_second, p_second) if L(p_second) != k-1: return insert(sigma_1, p_second, y) return append(sigma_2, p , p_second) if y == p_prime: return insert(sigma_1, p_prime, p_prime) if L(p_prime) != k-1: return insert(sigma_1, p_prime, y) return append(sigma_2, p, p_prime) def joinkcycles(cyclesk): cycles2k = [] for i in range(0,len(cyclesk),2): cycles2k += [cyclesk[i]+cyclesk[i+1]] return cycles2k def join(cycles2k, cyclesk): return normalize(joinkcycles(sorted(cycles2k))+cyclesk) def splet_2kcycles(sigma): cycles2k = [c for c in sigma if len(c) == 2*k] return [c[:k] for c in cycles2k] + [c[k:] for c in cycles2k] def hide_and_shift(sigma,i): n = size(sigma) cycleskothers = [c for c in sigma if len(c) == k if n not in c and i not in c] cycles = [cycleof(sigma,n), cycleof(sigma,i)] + splet_2kcycles(sigma) return join(cycles, cycleskothers) def split_and_shift(tau): gamma = largest_non_kcycles(tau) cycles2k = splet_2kcycles(tau) cycle_gamma = next(cycle for cycle in cycles2k if gamma in cycle) cycles2k.remove(cycle_gamma) cyclesk = [c for c in tau if len(c) == k] + [cycle_gamma, cycles2k[-1]] sigmaprime = join(cycles2k[:-1], cyclesk) return insert(sigmaprime, gamma, cycles2k[-1][1]) def shift(tau): gamma = largest_non_kcycles(tau) i = antecedent(tau, gamma) sigma = remove(tau, gamma) minsc = minimum_special_cycle(sigma) delta = minsc if minsc != 0 else i P = critical_elements(sigma) if i not in P: return insert(tau, delta, i) y = P.index(i) for l in range(y+1,len(P)): if P[l] > min(iterated_images(sigma,P[l-1],k-1)): break else: l = len(P) h = l-y a = min(iterated_images(sigma,P[l-1],k)) sigmaprime = insert(tau, a, gamma) sigmaprime = insert(sigmaprime, P[l-1], a) for j in range(l-1,l-h,-1): sigmaprime = insert(sigmaprime, P[j-1], P[j]) return insert(sigmaprime, delta, i) def inverse_shift(sigma): delta = minimum_special_cycle(sigma) gamma = largest_non_kcycles(sigma) i = image(sigma,delta) n = size(sigma) P = [0] + critical_elements(sigma) y = next((l for l in range(1,len(P)) if gamma in iterated_images(sigma,P[l],k-1))) if i > P[y]: return insert(sigma, antecedent(sigma, n), i) l = next(l for l in range(1,y+1) if P[l-1] < i < P[l]) sigmaprime = insert(sigma, antecedent(sigma, P[l]), i) for j in range(l, y): sigmaprime = insert(sigmaprime, P[j+1], P[j]) sigmaprime = insert(sigmaprime, n, P[y]) return insert(sigmaprime, i, n) #### Generation Tree def is_critical(sigma): return size(sigma) % k == 0 and not non_critical_cycles(sigma) def is_special(sigma): if size(sigma) % k != 0: sc = [cycle for cycle in sigma if len(cycle) < k] return len(sc) == 1 and not non_critical_cycles(cycle for cycle in sigma if cycle != sc[0]) return not non_critical_cycles(sigma) def generation_tree(sigma, i): n = size(sigma)+1 tau = insert(sigma, i, n) gamma = largest_non_kcycles(sigma) minsc = minimum_special_cycle(sigma) delta = minsc if minsc != 0 else i L = lambda i: 0 if i == n else len(cycleof(sigma,i)) if L(i) != k: l = L(i) zeta = tau elif L(i) == k and i < gamma: l = L(gamma) zeta = insert(tau, antecedent(sigma, gamma), i) else: l = 0 zeta = insert(tau, i, i) if l == k-1 and not is_special(sigma): return pop(zeta,i) if l == 2*k-1 and is_special(zeta) and n%k != 0: return inverse_shift(zeta) if l == 2*k-1 and is_special(zeta): return split_and_shift(zeta) if l == 2*k and is_special(sigma) and i > minimum_special_cycle(sigma) and n%k != 0: if L(i) == 2*k: return shift(zeta) return insert(tau, delta, i) if l == k-1 and is_special(sigma): if L(i) == k-1: return zeta return hide_and_shift(zeta,i) return zeta #### Random Generation def generate_random_permutation(n): sigma = [] for i in range(1,n+1): sigma = generation_tree(sigma, randint(1,i)) return sigma #### Classical Generation Trees # A permutation is just a list of values, ex: [2,1,3] for (1 2)(3). def last_value_insertion(sigma, i): sigma = sigma[:]+[i] for j in range(len(sigma)-1): if sigma[j] >= i: sigma[j] += 1 return sigma def knuth_shuffle(sigma, i): n = len(sigma)+1 if i != n: sigma = sigma[:] + [sigma[i-1]] sigma[i-1] = n else: sigma = sigma[:] + [n] return sigma ### Tikz tree generation def cycle_str(perm): return ''.join('('+''.join(map(str,c))+')' for c in perm) def table2cycle(perm): cycles = [] n = len(perm) visited = [False]*n for i in range(1,n+1): if not visited[i-1]: visited[i-1] = True c = [i] while perm[c[-1]-1] != i: visited[perm[c[-1]-1]-1] = True c += [perm[c[-1]-1]] cycles += [c] return cycles def print_tex_begin(f): print(r"\documentclass{standalone}", file=f) print(r"\usepackage{tikz-qtree}", file=f) print(r"\begin{document}", file=f) def print_tex_end(f): print("", file=f) print(r"\end{tikzpicture}", file=f) print(r"\end{document}", file=f) def print_tikz_preembule(n, f): print_tex_begin(f) print(r"\begin{tikzpicture}[grow=right, level distance=20mm]", file=f) print(r"\tikzset{every tree node/.style={font=\tiny}}", file=f) print(r"\tikzstyle{level 1}=[sibling distance=-1mm] ", file=f) print(r"\tikzstyle{level 2}=[sibling distance=-1.5mm]", file=f) print(r"\tikzstyle{level 3}=[sibling distance=-1.8mm]", file=f) print(r"\tikzstyle{level 4}=[sibling distance=-2.01mm]", file=f) print(r"\tikzstyle{level 5}=[sibling distance=-2.2mm]", file=f) print(r"\draw node at (0.5, "+str(0.1344*n*n)+r") {\underline{$k="+str(k)+"$}};", file=f) def print_tikz_generation_tree(n, borderlevel=False, f=sys.stdout): print_tikz_preembule(n, f) print(r"\tikzstyle{critical} = [color=red, font=\tiny \bfseries]", file=f) print(r"\tikzstyle{special} = [color=red]", file=f) print(r"\Tree", file=f) def print_tree_rec(p): if size(p) <= n : permstr = cycle_str(p) if size(p) != n and borderlevel else '.' if is_critical(p) : print(r"[.\node[critical]{"+permstr+"}; ", end="", file=f) elif is_special(p) : print(r"[.\node[special]{"+permstr+"}; ", end="", file=f) else: print("[.{"+permstr+"} ", end="", file=f) for i in range(1,size(p)+2): print_tree_rec(generation_tree(p, i)) print("]", end="", file=f) print_tree_rec([[1]]) print_tex_end(f) def print_tikz_classical_tree(n, tree, borderlevel=False, f=sys.stdout): print_tikz_preembule(n,f) print(r"\tikzstyle{changing} = [red, font=\tiny \bfseries]", file=f) print(r"\Tree", file=f) def nb_kcycles(sigma): return len([cycle for cycle in sigma if len(cycle)==k]) def print_tree_rec(p): if len(p) < n : kp = nb_kcycles(table2cycle(p)) for i in range(1,len(p)+2): child = tree(p, i) child_cycles = table2cycle(child) permstr = cycle_str(child_cycles) if len(child) != n and borderlevel else '.' if kp != nb_kcycles(child_cycles) : print(r"[.\node[changing]{"+permstr+"}; ", end="", file=f) else: print("[.{"+permstr+"} ", end="", file=f) print_tree_rec(child) print("]", end="", file=f) print(r"[.\node[changing]{(1)}; ",end="", file=f) print_tree_rec([1]) print(r"] ", end="", file=f) print_tex_end(f) def gentree(n, tree=generation_tree): allperm = [[] for j in range(n+1)] allperm[1].append(((1,),)) for m in range(1,n+1): for p in allperm[m]: for i in range(1,n+2): allperm[m+1].append( tree(p,i) ) print(p) from subprocess import call from sys import stdout def tikz_permutation(perm, scale=0.8, f=sys.stdout): print(r"\begin{tikzpicture}[thick, scale="+str(scale)+"]", file=f) i = 0 length = [1,1.75,2,3,4,4] offsets = [[(0,0)],[(0,1),(0,-1)],[(-0.75,0),(0.25,1),(0.25,-1)],[(-1,0),(0,1),(1,0),(0,-1)],\ [(-1.5,0),(-0.75,1),(0.75,1),(1.5,0),(0,-1)],\ [(-1.5,0),(-0.75,1),(0.75,1),(1.5,0),(0.75,-1),(-0.75,-1)]] for cycle in normalize(perm): l = len(cycle) i += length[l-1]/2 if l == 1: print(r"\node ("+str(cycle[0])+") at ("+str(i)+",0) {$"+str(cycle[0])+"$};", file=f) print(r"\draw[->] ("+str(cycle[0])+") edge [loop, looseness=5] ("+str(cycle[0])+");", file=f) else: for j in range(len(cycle)): pos = (i+offsets[l-1][j][0], offsets[l-1][j][1]) print(r"\node ("+str(cycle[j])+") at "+str(pos)+" {$"+str(cycle[j])+"$};", file=f) for j in range(len(cycle)): print(r"\draw[->] ("+str(cycle[j-1])+") edge [bend left] ("+str(cycle[j])+");", file=f) i += length[l-1]/2 print(r"\end{tikzpicture}", file=f) def tikz_permutations(perms, name="perm.tex", scale=0.8): f = open(name, 'w') print(r"\documentclass[varwidth]{standalone}", file=f) print(r"\usepackage{tikz-qtree}", file=f) print(r"\begin{document}", file=f) print(r"\begin{center}", file=f) for p in perms: tikz_permutation(p,scale,f) print(r"", file=f) print(r"\end{center}", file=f) print(r"\end{document}", file=f) f.close() call(["pdflatex","-interaction=batchmode", name]) def tikz_tree(n,K=1,algo=1,name="tree.tex"): f = open(name, 'w') global k k=K if algo == 1: print_tikz_generation_tree(n, True, f) elif algo == 2: print_tikz_classical_tree(n, last_value_insertion, True, f) else: print_tikz_classical_tree(n, knuth_shuffle, True, f) f.close() call(["pdflatex","-interaction=batchmode", name]) # New names merge = hide_and_shift cut = split_and_shift