#Version of May 8, 2003 #----------------------- Help ----------------------- Help:=proc(): print(` Version of May 8, 2003 `): if nargs=0 then print(` Welcome to JDT - A maple package written by `): print(` Rohan Fernandes - Humble student of Doron Zeilberger `): print(`Please send all bugs to rohanf@eden.rutgers.edu`): print(`It implements Schutzenberger's jeu-de-taquin`): print(``): print(`Contains the following procedures:`): print(` JDT, plotJDT, makePtableau`): #print(` `): elif nargs=1 then if args[1]=JDT then print(`This procedure performs Schutzenberger's jeu-de-taquin game`): print(`The input to this procedure is a pair of partitions`): print(`and the contents of the standard skew tableau`): print(`The output is resultant standard young tableau`): print(`and the sequence of jeu-de-taquin moves`): fi: if args[1]=makePtableau then print(`This procedure takes as input a permutation, `): print(`Then it creates an appropriate standard diagonal strip`): print(`tableau. On this it repeatedly calls the JDT procedure`): print(`to produce as output a plot of the activity of the JDT procedure`): print(`that can be animated. The final result is a P-tableau.`): fi: if args[1]=plotJDT then print(`This procedure prints the current state of the tableau `): print(`in the jeu-de-taquin algorithm.`): fi: fi: end: #--------------------- IsPar ----------------------- IsPar:= proc(lam)local i: #this procedure tests that lam valid if not type (lam,list) then #is lam a list? RETURN(false): fi: for i from 1 to nops(lam) do #are the list elements of lam integers? if not (type(lam[i], integer) and lam[i]>0) then RETURN(false): fi: od: for i from 1 to nops(lam) -1 do #is lam in the correct (non-increasing) order? if lam[i] - lam[i+1] < 0 then RETURN(false): fi: od: true: #if we pass the tests, then we've got it end: #IsPar #--------------------- Chop ----------------------- Chop:=proc(lam) local i: for i from 1 to nops(lam) while lam[i]>0 do od: i:=i-1: [op(1..i,lam)]: end: #Chop #------------------------------JDT----------------------------------------- JDT:=proc(lambda, mu, ST, locy, locx) local i,j, STL, mini, minj, min, sumlambda, lambda1, mu1, nmui, count1, count2, outplot,k : outplot:=[]: k:=1: lambda1:=lambda: mu1:=mu: STL:=ST: i:=locy: j:=locx: count1:=1: sumlambda:=STL[1,1]: while(count1 <= nops(STL)) do count2:=1: while(count2 <= nops(STL[count1])) do if sumlambda < STL[count1, count2] then sumlambda:=STL[count1, count2]: fi: count2:=count2+1: od: count1:=count1+1: od: sumlambda:=sumlambda+1: mu1[locy]:=mu1[locy]-1: STL[locy]:=[`?`,op(STL[locy])]: #print(`i and j are`,locy,locx): #print(`lambda1[i] is`,lambda1[i]): outplot:=[plotJDT(mu1,STL)]: while lambda1[i] >= j do min:=sumlambda: #print(`lambda1[i+1] is `,lambda1[i+1]): if i+1 <= nops(lambda1) and lambda1[i+1] >= j then mini:=i+1: minj:=j: if(i+1 <= nops(mu1)) then min:=STL[i+1,j-mu1[i+1]]: else min:=STL[i+1,j]: fi: #print(` min is `,min): fi: if(i > nops(mu1)) then nmui:=0 else nmui:=mu1[i]: fi: #print(`nmui is `, nmui): #print(`sumlambda is `, sumlambda): if lambda1[i] > j and STL[i, j+1-nmui] < min then #print(`STL[i, j+1-nmui] is`, STL[i, j+1-nmui]): min:=STL[i, j+1-nmui]: #print(`min is`, min): mini:=i: minj:=j+1: else if min = sumlambda then break: fi: #print(`j-mu1[i] is`, j-mu1[i]): if j-1-mu1[i] >=1 then STL[i]:=[ op(1..j-1-mu1[i], STL[i]),min,op(j+1-mu1[i]..nops(STL[i]),STL[i])]: else STL[i]:=[ min,op(j+1-mu1[i]..nops(STL[i]),STL[i])]: fi: i:=mini: j:=minj: if i <= nops(mu1) then STL[i, j-mu1[i]]:=`?`: else STL[i, j]:=`?`: fi: outplot:= [seq(outplot[k], k=1..nops(outplot)), plotJDT(mu1,STL)]: next: fi: if i <= nops(mu1) then STL[i, j-mu1[i]]:=min: STL[mini, minj-mu1[i]]:=`?`: else STL[i, j]:=min: STL[mini, minj]:=`?`: fi: i:=mini: j:=minj: outplot:= [seq(outplot[k], k=1..nops(outplot)), plotJDT(mu1,STL)]: od: #print(nops(outplot)): if(i <=nops(mu1)) then nmui:=mu1[i]: else nmui:=0: fi: #print(`i and j are`, i, j): if(j-1-nmui >=1) then STL[i]:=[seq(STL[i,k],k=1..j-1-nmui)]: #print(`STL[i] is` ,STL[i]): else STL[i]:=[]: fi: outplot:= [seq(outplot[k], k=1..nops(outplot)), plotJDT(mu1,STL)]: lambda1[i]:=lambda1[i]-1: #mu1[i]:=mu1[i]: #STL[i]:=[ op(1..nops(STL[i])-1, STL[i])]: lambda1:=Chop(lambda1): mu1:=Chop(mu1): #outplot:=plotJDT(mu1, STL): #lprint(outplot[1]): [lambda1,mu1,STL, outplot]: end: #JDT #---------------------makePtableau------------------------------- makePtableau:=proc(Pi) local i,j, STL, min, lambda1, mu1, temp, plot1 : plot1:=[]: lambda1:=[ seq(nops(Pi)-i+1,i=1..nops(Pi))]: mu1:=[ seq(nops(Pi)-i,i=1..nops(Pi)-1)]: STL:=[ seq([Pi[nops(Pi)-i+1]], i=1..nops(Pi))]: while nops(mu1) > 0 do for i from 1 to nops(mu1) do j:=mu1[i]: if mu1[i] > 0 then if i+1 > nops(mu1) then break: elif j > mu1[i+1] then break: fi: fi: od: #print(` i and j are pre JDT`,i,j): temp:=JDT(lambda1, mu1, STL, i, j): lambda1:=temp[1]: mu1:=temp[2]: STL:=temp[3]: if nops(plot1) > 0 then plot1:=[ seq(plot1[k], k=1..nops(plot1)), seq(temp[4,l], l=1..nops(temp[4]))]: else plot1:=temp[4]: fi: od: #display([seq(plot1[l],l=1..nops(plot1))], insequence): plot1: end: #makePtableau #-------------------------------plotJDT---------------------- plotJDT:=proc(mu, ST) local mu1, numST, numlist, i, j,k, outplot,STL: with(plots): mu1:=mu: STL:=ST: numST:=nops(STL): numlist:={}: if(nops(mu1) > 0) then for i from 1 to nops(mu1) do for j from 1 to mu1[i] do numlist:=`union`(numlist, {[j, numST-i+1,` `]}): #print(i,j,`?`): od: for j from 1 to nops(STL[i]) do numlist:=`union`(numlist,{[j+mu1[i], numST-i+1, STL[i,j]]}): #print(i,j+ mu1[i],STL[i,j]): od: od: fi: #print(nops(mu1),numST): for i from nops(mu1)+1 to numST do for j from 1 to nops(ST[i]) do numlist:=`union`(numlist,{[j, numST-i+1, ST[i,j]]}): #print(i,j,ST[i,j]): od: od: #print(numlist): textplot(numlist, axes=NONE): end: #plotJDT