attachment:jeu_taquin.py of days30_projects

   1 ####################################################################################
   2 #																				   #
   3 # Takes the poset, a vertex and a dictionary as input and returns a map (in the    #
   4 # form of a list) for making a new dictionary.									   #
   5 #																				   #
   6 ####################################################################################
   7 
   8 def assignment_map(pos,vert,dic,comp):
   9     upc=pos.upper_covers(vert)
  10     kgo=False
  11     next=None
  12     value=len(pos.list())+1
  13     
  14     for x in upc:
  15         a=x.element
  16         
  17         if dic[a][0]==comp and dic[a][1]<value:
  18             next=x
  19             value=dic[a][1]
  20     
  21     if next is not None:
  22         shift=[[dic[vert],(comp,value)]]
  23         kgo=True
  24     
  25     while kgo:
  26         upc=pos.upper_covers(next)
  27         
  28         if upc==[]:
  29             kgo=False
  30             shift.append([dic[next.element],dic[vert]])
  31         else:
  32             test=None
  33             value=len(pos.list())+1
  34             for x in upc:
  35                 a=x.element
  36                 if dic[a][0]==comp and dic[a][1]<value:
  37                     test=x
  38                     value=dic[a][1]
  39             if test is not None:
  40                 shift.append([dic[next.element],dic[test.element]])
  41                 next=test
  42             else:
  43                 kgo=False
  44                 shift.append([dic[next.element],dic[vert]])
  45     
  46     if next is not None:
  47         return shift
  48 	 
  49 ########################################################################################
  50 #																					   #
  51 # Gets a tuple corresponding to next poset											   #
  52 #																					   #
  53 ########################################################################################
  54 
  55 def get_vertex(dic,val,tag,istuple=True):
  56     V = dic.values()
  57     K = dic.keys()
  58     D2 = dict((V[i],K[i]) for i in xrange(len(V)))
  59     if istuple:
  60         return D2.get((tag,val))
  61     else:
  62         return D2.get(val)
  63 
  64 #######################################################################################
  65 #																					  #
  66 # Gets amount of elements in the ideal												  #
  67 #																					  #
  68 #######################################################################################
  69 def amount_ideal(dic,ideal):
  70     amount=0
  71     for i in xrange(len(dic)):
  72         if dic.values()[i][0]==ideal:
  73             amount += 1
  74     
  75     return amount
  76 
  77 #######################################################################################
  78 #																					  #
  79 # Creates a new dictionary with the input map										  #
  80 #																					  #
  81 #######################################################################################
  82 
  83 def dic_shift(map,dic):
  84     for pos_key in dic.iterkeys():
  85         for map_el in map:
  86             if dic[pos_key]==map_el[0]:
  87                 dic[pos_key]=map_el[1]
  88                 break
  89     return dic
  90 
  91 #######################################################################################
  92 #																					  #
  93 # Jeu de taquin function. Plays out jeu de taquin for poset.						  #
  94 #																					  #
  95 # dictionary must be of the form: D1 = {(0,0):('a',1), (0,1):('a',2), (1,0):('a',3),  #
  96 # (2,0):('a',4), (1,1):('b',1), (2,1):('b',2), (0,2):('b',3), (1,2):('b',4),		  #
  97 # (2,2):('b',5)}																	  #
  98 #																					  #
  99 #######################################################################################
 100 
 101 def jeu_taquin(pos,dic,ideal='a',comp='b'):
 102     newdic = dic
 103     length = amount_ideal(dic,ideal)
 104     
 105     for i in xrange(length,0,-1):
 106         ver=get_vertex(newdic,i,ideal)  # gets a tuple representing a vertex in the ideal
 107         map=assignment_map(pos,ver,newdic,comp) # creates a map for modifying the dict.
 108         newdic=dic_shift(map,newdic) # creates a new dictionary with the map
 109     
 110     return newdic
 111 	
 112 ########################################################################################
 113 #																					   #
 114 # Promoter function. Given a numbered poset, plays out one promotion.				   #
 115 #																					   #
 116 # dictionary must be of the form: 
 117 #
 118 #
 119 ########################################################################################
 120 			
 121 			
 122 def promoter(pos,dic):
 123     dic[get_vertex(dic,1,None,istuple=False)]=('a',1)
 124     
 125     for i in range(2,len(pos.list())+1):
 126         dic[get_vertex(dic,i,None,istuple=False)]=('b',i-1)
 127     
 128     dic=jeu_taquin(pos,dic)
 129     
 130     dic[get_vertex(dic,1,'a')]=len(pos.list())
 131     
 132     for i in range(1,len(pos.list())):
 133         dic[get_vertex(dic,i,'b')]=i
 134 
 135 #########################################################################################
 136 #																						#
 137 # Executes n promotions on the input poset												#
 138 #																						#
 139 #########################################################################################
 140 
 141 def promotion_loop(pos,dic,n):
 142     set=pos
 143     for i in range(n):
 144         set=promoter(set,dic)
 145     
 146     return set	
 147