#M10.txt: Maple Code for Lecture 9 of Math 454,Combinatorics, Rutgers University, taught by Dr. Z. (Doron Zeilberger)
Help10:=proc():print(` MulPers(P1,P2) , InvPer(P) , GrabCycle(P,i), PtoC(P), CtoP(C), FunT(pi),  GG(S) , inv(pi), maj(pi) , FunT(pi)  `):
end:

with(combinat):

#MulPers(P1,P2): Inputs permutations P1 and P2 of {1, ..., n} and outputs their product
#For example, try:
#MulPers([2,3,1],[3,1,2]);
MulPers:=proc(P1,P2) local n,i:
#The first few lines checks that the input is correct
 if not (type(P1,list) and type(P2,list)) then
  print(`Bad input`):
  RETURN(FAIL):
 fi:
n:=nops(P1):

if  not (convert(P1,set)={seq(i,i=1..n)} and convert(P2,set)={seq(i,i=1..n)} ) then
  print(`Bad input`):
  RETURN(FAIL):
 fi:

[seq(P2[P1[i]],i=1..n)]:


end:

#InvPer(P): The inverse of the permutation P
InvPer:=proc(P) local i,n,T:
 if not type(P,list) then
  print(`Bad input`):
  RETURN(FAIL):
 fi:

n:=nops(P):
if  not convert(P,set)={seq(i,i=1..n)}  then
  print(`Bad input`):
  RETURN(FAIL):
 fi:

#Recalling the list P is the function that maps i to P[i], we define a TABLE (a Maple Data structure) that
#maps P[i] to i

for i from 1 to n do
 T[P[i]]:=i:
od:

#We convert it back into a list
[seq(T[i],i=1..n)]:
end:

#GrabCycle(P,i): inputs a permutation P of {1, ...,n} and outputs the cycle belonging to i. 
#We use the convention that it starts with the largest entry
#Try
#GrabCycle([3,1,4,2],2);
GrabCycle:=proc(P,i) local C,j:

#We view the cycle belnging to i as a list, starting at i
C:=[i]:

#We find where i points to, call it j
j:=P[i]:

while j<>i do
#sooner or later we will wind back at i (since the permutation is finite) so we append the new
#arrivals to the list C and rename j
C:=[op(C),j]:
j:=P[j]:
od:

#We look at the place where it it is max
j:=max[index](C):

#we rewrite the cycle with the largest entry first

[op(j..nops(C),C),op(1..j-1,C)]:

end:

#PtoC(P): Inputs a permutation P outputs its list of cycles. Try:
#PtoC([2,1,3,4]);
PtoC:=proc(P) local n,StillToDo,L,i,C,L1,T:

n:=nops(P):

StillToDo:={seq(i,i=1..n)}:

#L is a dynamically construcete list of cycles in the permutatib P, we start with the empty list
#until no one is left
L:=[]:

while StillToDo<>{} do
#we pick the smallest survivor
 i:=min(op(StillToDo)):
 #we grab its cycle
 C:=GrabCycle(P,i):

# We append C to L
 L:=[op(L),C]:

#We update StillToDo by kicking out the members of C

StillToDo:= StillToDo minus convert(C,set):
od:

#So far L is a list of cycles but arranged in a random order
#Now we arrange them according to the convention that the first (largest) entries are increasing
#L1 is the list of first (largest) entries of each cycle:
L1:=[seq(L[i][1],i=1..nops(L))]:

#We now make a table where T[a] is the cycle that starts with  a
for i from 1 to nops(L) do
 T[L[i][1]]:=L[i]:
od:

#Now we sort L1
L1:=sort(L1):

#Now we rewrite L with the above convention
[seq(T[L1[i]],i=1..nops(L1))]:

end:


#FunT(P): The fundamental transformation
FunT:=proc(P) local P1,i:
P1:=PtoC(P):
[seq(op(P1[i]),i=1..nops(P1))]:
end:

#GG(S): inputs a pos.  integer n and a set of permutations in {1,..n} outputs the subgroup generated by them
GG:=proc(S) local Gr,s,g,Gr1,Gr2:
Gr:=S:
Gr1:=Gr union {seq(seq(MulPers(s,g), s in S), g in Gr)}:

while Gr<>Gr1 do
Gr2:=Gr1 union {seq(seq(MulPers(s,g), s in S), g in Gr1)}:
Gr:=Gr1:
Gr1:=Gr2:
od:
Gr1:

end:


#inv(pi): The number of inversion of a permutation pi
inv:=proc(pi) local n,i,j,co:
n:=nops(pi):
co:=0:

for i from 1 to n do
 for j from i+1 to n do
   if pi[i]>pi[j] then
    co:=co+1:
   fi:
 od:
od:

co:

end:


#maj(pi): The major index a permutation pi
maj:=proc(pi) local n,i,co:
n:=nops(pi):
co:=0:

for i from 1 to n-1 do
   if pi[i]>pi[i+1] then
    co:=co+i:
   fi:
 od:


co:

end:

#CtoP(C): Inputs a permutation in cycle structre , outputs it in 1-line notation
#Try([[1],[3,2]]);
CtoP:=proc(C) local i,L,n,T,C1,j:
L:=[seq(op(C[i]),i=1..nops(C))]:
n:=nops(L):

if convert(L,set)<>{seq(i,i=1..n)} then
  RETURN(FAIL):
fi:

for i from 1 to nops(C) do
 C1:=C[i]:
 for j from 1 to nops(C1)-1 do
   T[C1[j]]:=C1[j+1]:
 od:
 T[C1[nops(C1)]]:=C1[1]:
od:

[seq(T[i],i=1..n)]:
end: