######################################################################
## BalT.txt Save this file as   BalT.txt to use it,                  #
# stay in the                                                        #
## same directory, get into Maple (by typing: maple <Enter> )        #
## and then type:  read `BalT.txt` <Enter>                           #
## Then follow the instructions given there                          #
##                                                                   #
## Written by Doron Zeilberger, Rutgers University ,                 #
##  DoronZeil at gmail dot com                                       # 
######################################################################



print(`First Written: June 2022: tested for Maple 2020 `):
print(`Version  : June 2022  `):
print():
print(`This is BalT.txt, one of the  Maple packages that`):
print(`accompany Shalsoh B. Ekhad and Doron Zeilberger's  article: `):
print(` Experimenting with reduced decompositions in the Symmetric Group`):

print():
print(`The most current version is available on WWW at:`):
print(` http://sites.math.rutgers.edu/~zeilberg/tokhniot/VicR.txt .`):
print(`Please report all bugs to: DoronZeil at gmail dot com .`):

print():
print(`For general help, and a list of the MAIN functions,`):
print(` type "ezra();". For specific help type "ezra(procedure_name);" `):

print(`--------------------------`):
print(`For a list of the supporting functions type: ezra1();`):
print(`For help with a specific procedure type:`):
print(`ezra(ProcedureName);`):
print(`--------------------------`):

print(`--------------------------`):
print():
print(`For a list of the Stanley Soliratire functions type: ezraSS();`):
print(`For help with a specific procedure type:`):
print(`ezra(ProcedureName);`):

print():
print(`--------------------------`):


print(`--------------------------`):
print():
print(`For a list of the General tableaux functions type: ezraG();`):
print(`For help with a specific procedure type:`):
print(`ezra(ProcedureName);`):

print():
print(`--------------------------`):




ezra1:=proc()
if args=NULL then

print(`The SUPPORTING procedures are: `):
print(` AllBTslow, Arm, ChaBT, Conj, GenBT1, IsBa, Kids, Kids1, Leg, PrT, RAN, YF `):

else
ezra(args):

fi:


end:



ezraSS:=proc()
if args=NULL then

print(`The Stanely Solitaire procedures are: `):
print(` GenSS, KidsSS, SScha, SSnu `):

else
ezra(args):

fi:


end:


ezraG:=proc()
if args=NULL then

print(`The General Tableaux rocedures are: `):
print(` HookT, RandTab  `):

else
ezra(args):

fi:


end:


ezra:=proc()
if args=NULL then

print(` BalT.txt: A Maple package for studying Balanced tableaux introduced by Paul Edelman and Curtis Greene `):

print(`The MAIN procedures are:  `):
print(` AllBT, BTnu `):




elif nargs=1 and args[1]=AllBTslow then
print(`AllBTslow(L): All the balanced tableax of shape L. Try:`):
print(`DONE Slowly. Only for checking puropses. Try:`):
print(`AllBTslow([3,2,1]);`):


elif nargs=1 and args[1]=AllBT then
print(`AllBT(L): All the balanced tableax of shape L, via dynamical programming. Try:`):
print(`AllBT([3,2,1]);`):


elif nargs=1 and args[1]=AllBTc then
print(`AllBTc(L): All the balanced tableax of shape L, represented as chains of states. Try:`):
print(`AllBTc([3,2,1]);`):

elif nargs=1 and args[1]=Arm then
print(`Arm(L,c): The arm-length of the cell c in the shape L. Try: `):
print(`Arm([4,3,2],[2,2]);`):


elif nargs=1 and args[1]=BTnu then
print(`BTnu(L): the number of balanced tableax of shape L, via dynamical programming. Try:`):
print(`BTnu([3,2,1]);`):

elif nargs=1 and args[1]=ChaBT then
print(`ChaBT(L,T): All the balanced tableaux chains  chains starting at the state T. Try:`):
print(`ChaBT([3,2,1],[[0,0,0],[0,0],[0]]);`):


elif nargs=1 and args[1]=Conj then
print(`Conj(L): The conjugate of the partition L. Try:`):
print(`Conj([5,4,3]);`):


elif nargs=1 and args[1]=HookT then
print(`HookT(T): Given a tableau T outputs the Rank table. Try:`):
print(`HookT([[3,5,6],[2,4],[1]]);`):


elif nargs=1 and args[1]=GenBT1 then
print(`GenBT1(L,k): all the descendants of the balanced tableux state L, Try:`):
print(`GenBT([[0,0,0],[0,0]],2);`):

elif nargs=1 and args[1]=GenSS then
print(`GenSS(L,k): all the descendants of the state L in Stanely Solitaire, L at the k-th generation, Try:`):
print(`GenSS([3,2,0,0,0],2);`):

elif nargs=1 and args[1]=IsBa then
print(`IsBa(T): Is the tableu T balanced?. try:`):
print(` IsBa([[3,5,6],[2,4],[1]]);`):

elif nargs=1 and args[1]=Kids then
print(`Kids(T): given a partially filled balanced tableu finds all its continuations. Try:`):
print(`Kids([[0,5,6],[0,0],[0]]);`):

elif nargs=1 and args[1]=Kids1 then
print(`Kids1(T): given a general shape consisting of 0 and n's finds all its legal children`):
print(`Kids1([[0,6,6],[0,0],[0]]);`):

elif nargs=1 and args[1]=KidsSS then
print(`KidsSS(L) All the children of the state L, try:`):
print(`KidsSS([3,2,0,0,0]);`):

elif nargs=1 and args[1]=Leg then
print(`Leg(L,c): The leg-length of the cell c in the shape L. Try: `):
print(`Leg([4,3,2],[2,2]);`):

elif nargs=1 and args[1]=PrT then
print(`PrT(T): prints the tablea T nicely. Try:`):
print(`PrT([[1,2,5],[3,4]]);`):


elif nargs=1 and args[1]=RAN then
print(`RAN(L,a): The rank of the item a in the list L. Try:`):
print(`RAN([5,1,3,2],2);`):

elif nargs=1 and args[1]=RandTab then
print(`RandTab(L): R random tableau of shape L (no restrictions). Try:`):
print(`RandTab([3,3,3]);`):


elif nargs=1 and args[1]=SScha then
print(`SScha(L): all the ways to play Stanley Solitaire with starting position L. Try:`):
print(`SScha([4,3,0,0,0,0]);`):

elif nargs=1 and args[1]=SSnu then
print(`SSnu(L): The number of ways to play Stanley Solitaire with starting position L. Try:`):
print(`SSnu([3,2,0,0,0]);`):

elif nargs=1 and args[1]=YF then
print(`YF(L): The Young-Frobenius formula. Try: `):
print(`YF([4,3,2]);`):




else
 print(`There is no such thing as`, args):

fi:


end:


with(combinat):


#YF(L): The Young-Frobenius formula
YF:=proc(L) local i,j,n,k:
n:=convert(L,`+`):
k:=nops(L):
n!/mul((L[i]+k-i)!,i=1..k)*mul(mul((L[j]+k-j)-(L[i]+k-i),j=1..i-1),i=1..k):
end:

#Conj(L): The conjugate of the shape L. Try:
#Conj([5,5,3]);
Conj:=proc(L) local L1,i,k:
option remember:
if L=[] then
 RETURN([]):
fi:
k:=nops(L):
L1:=L-[1$k]:
for  i from 1 to k while L1[i]>0 do od:
L1:=[op(1..i-1,L1)]:
[k,op(Conj(L1))]:
end:

#Arm(L,c): Given a cell c, finds its arm
Arm:=proc(L,c) local i,j:
i:=c[1]:
j:=c[2]:
if not (i<=nops(L) and  j<=L[i]) then
 RETURN(FAIL):
fi:
L[i]-j+1:
end:


#Arm(L,c): Given a cell c, finds its arm
Arm:=proc(L,c) local i,j:
i:=c[1]:
j:=c[2]:
if not (i<=nops(L) and  j<=L[i]) then
 RETURN(FAIL):
fi:
L[i]-j+1:
end:


#Leg(L,c): Given a cell c, finds its arm
Leg:=proc(L,c) local i,j,L1:
i:=c[1]:
j:=c[2]:
if not (i<=nops(L) and  j<=L[i]) then
 RETURN(FAIL):
fi:
L1:=Conj(L):
L1[j]-i+1:
end:

#RAN(L,a): The rank of the item a in the list L. Try:
#RAN([5,1,3,2],2);
RAN:=proc(L,a) local L1,i:


if not member(a,{op(L)}) then
 RETURN(FAIL):
fi:

L1:=sort(L):

for i from 1 to nops(L) while L1[i]<>a do od:
i:
end:

#IsBa(T): Given a tableau T checks whether it is a balanced tableau. Try:
#IsBa([[3,5,6],[2,4],[1]]);
IsBa:=proc(T) local L,c,i,j,i1,j1,n,H,L1:
L:=[seq(nops(T[i]),i=1..nops(T))]:
L1:=Conj(L):
n:=convert(L,`+`):
if {seq(op(T[i]),i=1..nops(T))}<>{seq(i,i=1..n)} then
 RETURN(false):
fi:

for i from 1 to nops(T) do
for j from 1 to nops(T[i]) do
c:=[i,j]:
H:=[seq(T[i][j1],j1=j..L[i]), seq(T[i1][j],i1=i+1..L1[j])]:
 if RAN(H,T[i][j])<>Leg(L,c) then
  RETURN(false):
 fi:
od:
od:

true:

end:

#AllBTslow(L): All the balanced tableax of shape L. Try:
#DONE Slowly. Only for checking puropses. Try:
#AllBTslow([3,2,1]);

AllBTslow:=proc(L) local n,mu,mu1,co,i,j,gu,T,T1:
n:=convert(L,`+`):
mu:=permute(n):
gu:={}:
for mu1 in mu do
co:=1:
T:=[]:
for i from 1 to nops(L) do
T1:=[]:

for j from 1 to L[i] do
T1:=[op(T1),mu1[co]]:
co:=co+1:
od:
T:=[op(T),T1]:
od:
if IsBa(T) then
 gu:=gu union {T}:
fi:

od:

gu:
end:

#Kids(T): given a partially filled balanced tableu finds all its continuations. Try:
#Kids([[0,5,6],[0,0],[0]]);
Kids:=proc(T) local gu,i,j,m,L,n,L1,i1,j1,H,T1,c:
L:=[seq(nops(T[i]),i=1..nops(T))]:
L1:=Conj(L):
n:=convert(L,`+`):

if {seq(op(T[i]),i=1..nops(T))}={0} then
 m:=n:
else
m:=min({seq(op(T[i]),i=1..nops(T))} minus {0})-1:
fi:

gu:={}:

for i from 1 to nops(L) do
 for j from 1 to L[i] do
 c:=[i,j]:
  if T[i][j]=0 then
    T1:=[op(1..i-1,T),[op(1..j-1,T[i]), m, op(j+1..L[i],T[i])],op(i+1..nops(T),T)]:

 H:=[seq(T1[i][j1],j1=j..L[i]), seq(T1[i1][j],i1=i+1..L1[j])]:
 if RAN(H,T1[i][j])=Leg(L,c) then
  gu:=gu union {T1}:
 fi:
 fi:
od:
od:
gu:
end:



#AllBT(L): All the balanced tableax of shape L. Try:
#AllBT([3,2,1]);
#DONE Faste
AllBT:=proc(L) local gu,n,T,gu1,i:
 n:=convert(L,`+`):
 T:=[seq([0$L[i]],i=1..nops(L))]:
 gu:={T}:

for i from 1 to n do
 gu:={seq(op(Kids(gu1)),gu1 in gu)}:
od:

gu:
end:





#Kids1(T): given a general shape consisting of 0 and n's finds all its legal children
#Kids1([[0,6,6],[0,0],[0]]);
Kids1:=proc(T) local gu,i,j,L,n,L1,i1,j1,H,T1,c:
L:=[seq(nops(T[i]),i=1..nops(T))]:
L1:=Conj(L):
n:=convert(L,`+`):

gu:={}:

for i from 1 to nops(L) do
 for j from 1 to L[i] do
 c:=[i,j]:
  if T[i][j]=0 then
    T1:=[op(1..i-1,T),[op(1..j-1,T[i]), n, op(j+1..L[i],T[i])],op(i+1..nops(T),T)]:

 H:=[seq(T1[i][j1],j1=j..L[i]), seq(T1[i1][j],i1=i+1..L1[j])]:
 if RAN(H,T1[i][j])=Leg(L,c) then
  gu:=gu union {T1}:
 fi:
 fi:
od:
od:
gu:
end:

#ChaBT(L,T): All the balanced tableaux chains  chains starting at T
ChaBT:=proc(L,T) local n,gu,mu,mu1,gu1, gu11,i:
option remember:
n:=convert(L,`+`):
if T=[seq([n$L[i]],i=1..nops(L))] then
  RETURN({[T]}):
fi:

mu:=Kids1(T):

gu:={}:

for mu1 in mu do
 gu1:=ChaBT(L,mu1):
 gu:=gu union {seq([T,op(gu11)],gu11 in gu1)}:
od:
gu:

end:

#AllBTc(L):  All the balanced tableax of shape L in terms of chains
AllBTc:=proc(L) local i:
 ChaBT(L,[seq([0$L[i]],i=1..nops(L))]):
end:



#ChaNu(L,T): the number of balanced tableaux chains  starting at T
ChaNu:=proc(L,T) local n,i,mu,mu1:
option remember:
n:=convert(L,`+`):
if T=[seq([n$L[i]],i=1..nops(L))] then
  RETURN(1):
fi:

mu:=Kids1(T):

add(ChaNu(L,mu1),mu1 in mu):


end:


BTnu:=proc(L)  local i:
 ChaNu(L,[seq([0$L[i]],i=1..nops(L))]):
end:

#PrT(T): prints the tableau T
PrT:=proc(T) local i:
for i from 1 to nops(T) do
lprint(op(T[i])):
od:
end:

##Start Stanley Solitaire


#KidsSS(L) All the children of the state L, try:
#KidsSS([3,2,0,0,0]);
KidsSS:=proc(L) local gu,i:
option remember:
gu:={}:

if L=[0$nops(L)] then
 RETURN({}):
fi:

for i from 1 to nops(L)-1 do
 if L[i]>L[i+1] then
  gu:=gu union {[op(1..i-1,L),L[i+1],L[i]-1,op(i+2..nops(L),L)]}:
 fi:
od:
gu:
end:


#SSnu(L): The number of ways to play Stanley Solitaire with starting position L. Try:
#SSnu([3,2,0,0,0]);

SSnu:=proc(L)  local gu,gu1:
option remember:
if L=[0$nops(L)] then
 RETURN(1):
else
gu:=KidsSS(L):

add(SSnu(gu1),gu1 in gu):
fi:

end:


#SScha(L): all the ways to play Stanley Solitaire with starting position L. Try:
#SScha([4,3,0,0,0,0]);
SScha:=proc(L) local gu,mu,mu1,gu1,gu11:
option remember:

if L=[0$nops(L)] then
 RETURN({[L]}):
fi:
gu:={}:

mu:=KidsSS(L):

for mu1 in mu do
 gu1:=SScha(mu1):
 gu:=gu union {seq([L,op(gu11)],gu11 in gu1)}:
od:
gu:
end:


#GenSS(L,k): all the descendants of L at the k-th generation, Try:
#GenSS([3,2,0,0,0],2);
GenSS:=proc(L,k) local gu,gu1:
option remember:
if k=0 then
 RETURN({L}):
fi:

gu:=GenSS(L,k-1):

{seq(op(KidsSS(gu1)),gu1 in gu)}:
end:





#GenBT1(L,k): all the descendants of the state L at the k-th generation. Try:
#GenBT1([[0,0,0],[0,0]],2);
GenBT1:=proc(L,k) local gu,gu1:
option remember:
if k=0 then
 RETURN({L}):
fi:

gu:=GenBT1(L,k-1):

{seq(op(Kids1(gu1)),gu1 in gu)}:
end:



##End Stanley Solitaire



##start General Tableaux

#RandTab(L): R random tableau of shape L (no restrictions). Try:
#RandTab([3,3,3]);
RandTab:=proc(L) local pi,i,j,T,T1,co:
pi:=randperm(convert(L,`+`)):

T:=[]:

co:=0:
for i from 1 to nops(L) do
T1:=[]:
for j from 1 to L[i] do
 co:=co+1:
 T1:=[op(T1),pi[co]]:
od:
T:=[op(T),T1]:
od:

T:
end:








#HookT(T): Given a tableau T outputs the Rank table. Try:
#HookT([[3,5,6],[2,4],[1]]);
HookT:=proc(T) local L,c,i,j,i1,j1,n,H,L1,TAB,TAB1:
L:=[seq(nops(T[i]),i=1..nops(T))]:
L1:=Conj(L):
n:=convert(L,`+`):
if {seq(op(T[i]),i=1..nops(T))}<>{seq(i,i=1..n)} then
 RETURN(FAIL):
fi:

TAB:=[]:
for i from 1 to nops(T) do
TAB1:=[]:
for j from 1 to nops(T[i]) do
 c:=[i,j]:
 H:=[seq(T[i][j1],j1=j..L[i]), seq(T[i1][j],i1=i+1..L1[j])]:
 TAB1:=[op(TAB1),RAN(H,T[i][j])]:
od:
TAB:=[op(TAB),TAB1]:
od:

TAB:

end:


#End General Tableaux