#OK to post homework
#Wanying Rao, 02/06/2021, Assignment 5

Help := proc(): print(`PermuG(n), NextPG(pi), PrevPG(pi), MyRandPermA(n), MyRandPermI(n)`):end:

#1
#PermuG(n): Inputs a non-negative integer n and outputs a list of all permutations of #{1,...,n} such that when you move along the list the next permutation is 
#an adjacent transposition
PermuG := proc(n)  local k,S,i,pi,pi1,L,j:
option remember:

if n=0 then
 RETURN([[]]):
fi:

S:=PermuG(n-1):

L:=[]:

for i from 1 to nops(S) do
 pi:=S[i]:
 for j from 1 to n do
  if irem(i,2) = 0 then
   pi1 := [op(1..j-1,pi),n,op(j..nops(pi),pi)]: 
  else
   pi1 := REV([op(1..j-1,REV(pi)),n,op(j..nops(pi),REV(pi))])
  fi:
  L := [op(L),pi1]:
 od:
od:

L:
end:

#2
#R(L): Inputs a list L of a permutation {1..n} and outputs the number of inversions.
#For example [1,4,2,3]. we have 2 inversions 42,43, thus R([1,4,2,3])=2
R := proc(L) local i,n:
n := nops(L):
if n = 0 then
 RETURN(0):
else
 i := 1:
 while L[i]<>n do
  i := i+1:
 od:
 RETURN(n-i+R([op(1..i-1,L),op(i+1..n,L)])):
fi: 
end:

#NextPG(pi):Inputs a permutation pi of {1, ...,n} for some n, and outputs the ones that #come right after it in the above PermuG(n)
NextPG := proc(pi) local n,i:
n := nops(pi):
i := 1:
if pi[1]=n and irem(R([op(2..n,pi)]),2)=0 then
 RETURN([n,op(NextPG(pi[2..n]))]):
else 
 while i <= n do
  if pi[i] = n and irem(R([op(1..i-1,pi),op(i+1..n,pi)]),2) = 0 then
   RETURN([op(1..i-2,pi),pi[i],pi[i-1],op(i+1..n,pi)]):
  elif pi[i] = n and irem(R([op(1..i-1,pi),op(i+1..n,pi)]),2) = 1 then
   RETURN([op(1..i-1,pi),pi[i+1],pi[i],op(i+2..n,pi)])
  else
   i := i+1:
  fi:
 od:
fi:
end:


#PrevPG(pi):Inputs a permutation pi of {1, ...,n} for some n, and outputs the ones that #come right before it in the above PermuG(n)
PrevPG := proc(pi) local n,i:
n := nops(pi):
i := 1:
if pi[1]=n and irem(R([op(2..n,pi)]),2)=1 then
 RETURN([n,op(PrevPG(pi[2..n]))]):
else 
 while i <= n do
  if pi[i] = n and irem(R([op(1..i-1,pi),op(i+1..n,pi)]),2) = 1 then
   RETURN([op(1..i-2,pi),pi[i],pi[i-1],op(i+1..n,pi)]):
  elif pi[i] = n and irem(R([op(1..i-1,pi),op(i+1..n,pi)]),2) = 0 then
   RETURN([op(1..i-1,pi),pi[i+1],pi[i],op(i+2..n,pi)])
  else
   i := i+1:
  fi:
 od:
fi:end:

#3
MyRandPermA := proc(n) local r,s,J:
if n=1 then
 RETURN([1]):
else
 r := rand(1..n)():
 s := MyRandPermA(n-1):
 J := [seq(1..r-1),seq(r+1..n)]:
RETURN([r,op(Expa(s,J))]):
fi:
end:

MyRandPermI := proc(n) local r,s:
if n=1 then
 RETURN([1]):
else
 r := rand(1..n)():
 s := MyRandPermI(n-1):
 RETURN([op(1..r-1,s),n,op(r..n-1,s)]):
fi:
end:


#4
NoABC := proc(n) local N,S,i,pi,pi1,pi2,pi3,L,j,i1:

option remember:
if n=0 then
 RETURN([[]]):
fi:

if n=1 then
 RETURN([[1]]):
fi:

if n=2 then
 RETURN([[1,2],[2,1]]):
fi:

if n=3 then
 RETURN([[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]):
fi:

S := PermuI(n-1):
N := NoABC(n-1):

if n>3 then
 L := []:
 for pi in N do
  for j from 1 to n do
   pi1:=[op(1..j-1,pi),n,op(j..nops(pi),pi)]:
   L:=[op(L),pi1]:
  od:
 od:
 for pi in convert(S,set) minus convert(N,set) do
  i := 1:
  while pi[i]<>1 do
   i := i+1:
  od:
  pi2 := [op(1..i,pi),n,op(i+1..nops(pi),pi)]:
  pi3 := [op(1..i+1,pi),n,op(i+2..nops(pi),pi)]:
  L :=[op(L),pi2,pi3]:
 od:
 RETURN(L):
fi:

end:

#The result of [seq(nops(NoABC(n)),n=1..8)] is [1,2,5,22,114,696,4920,39600].


#####C5#####
#C5.txt: Maple Code for Lecture 5
Help5:=proc(): print(`Redu(L), Expa(pi,S), PermuA(n),PermuI(n) `): end:

#Redu(L): inputs a list L of numbers and outputs
#The multi-set permuation of {1, ...,nops({op(L)}) where n is the number of
#number of 
#distinct members of L and the smallest number in {op(L)}
#replaced by 1, the second smallest by 2, etc.
#For example
#Redu([evalf(Pi),evalf(Pi),evalf(exp(1)),evalf(exp(1))]
#should return
#[2,2,1,1]
##Redu([evalf(Pi),evalf(exp(1)),evalf(exp(1)),5]
#=[2,1,1,3]
#
Redu:=proc(L) local S,T,i:
S:=sort(convert({op(L)},list)):

for i from 1 to nops(S) do
 T[S[i]]:=i:
od:

[seq(T[L[i]],i=1..nops(L))]:

end:

#Expa(pi,S): inputs a permutation pi of 1,..., nops(pi) and
#a sorted list of distinct numbers S, replaces 1 by
#the smallest member of S, etc. 
#For example
#Expa([2,1,3],[11,13,15])= [13,11,15]
Expa:=proc(pi,S) local i:
subs({seq(i=S[i],i=1..nops(S))},pi):
end:

#PermuA(n): inputs a non-neg. integer n and outputs the list of
#all n! permutations of {1,...,n} in lex-order (same as permute(n) in combinat)
PermuA:=proc(n) local S,L,j, J,pi:
option remember:
if n=0 then
 RETURN([[]]):
fi:

S:=PermuA(n-1):

L:=[]:


for j from 1 to n do
  #J:=1...j-1,j+1..n
  J:=[seq(1..j-1), seq(j+1..n)]:
   L:= [op(L),seq([ j, op(Expa(S[i],J)) ],i=1..nops(S))] :
od:
L:
end:

#PermuI(n): the list of all permutations of {1, ...,n} using inertion
PermuI:=proc(n)  local S,i,pi,pi1,L,j,i1:

option remember:
if n=0 then
 RETURN([[]]):
fi:


S:=PermuI(n-1):

L:=[]:

for i from 1 to nops(S) do
pi:=S[i]:

for j from 1 to n do
 pi1:=[op(1..j-1,pi),n,op(j..nops(pi),pi)]:
 L:=[op(L),pi1]:
od:
od:

L:
end:


#REV(L) from C3.txt
REV:=proc(L) local i: [seq(L[-i],i=1..nops(L))]:end: