#OK to post
#Yuxuan Yang, Feb 6th, Assignment 5 

with(combinat):

#1
PermuG:=proc(n)  local S,i,pi,pi1,L,j,i1:
option remember:
if n=0 then
 RETURN([[]]):
fi:
S:=PermuG(n-1):
L:=[]:
for i from 1 to nops(S) do
pi:=S[i]:
if i mod 2 = 0 then
for j from 1 to n do
 pi1:=[op(1..j-1,pi),n,op(j..nops(pi),pi)]:
 L:=[op(L),pi1]:
od:
else
for j from 1 to n do
 pi1:=[op(1..n-j,pi),n,op(n+1-j..nops(pi),pi)]:
 L:=[op(L),pi1]:
od:
fi:
od:
L:
end:

#2 No idea how to find NextPG without using PermuG	

#3
MyRandPermA:=proc(n) local S,c,i,j,J:
if n=0 then 
 RETURN([]):
fi:

S:=MyRandPermA(n-1):
c:=rand(1..n)():
J:=[seq(1..c-1), seq(c+1..n)]:
[c, op(Expa(S,J))]:
end:

MyRandPermI:=proc(n) local S,c:
if n=0 then 
 RETURN([]):
fi:

S:=MyRandPermI(n-1):
c:=rand(1..n)():

[op(1..c-1,S),n,op(c..nops(S),S)]:
end:
#randperm is much faster, 1000000 is too large for recursion.


#4
NoABC:=proc(n)  local S,i,pi,pi1,L,j,i1:
option remember:
if n=0 then
 RETURN([[]]):
fi:


S:=NoABC(n-1):

L:=[]:

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

for j from 1 to n do
if sort([op(1..j-1,pi)], `>`)=[op(1..j-1,pi)] then
 pi1:=[op(1..j-1,pi),n,op(j..nops(pi),pi)]:
 L:=[op(L),pi1]:
fi:
od:
od:

L:
end:

#Catalan numbers. The results can be found in the following paper.
#PERMUTATION PATTERN AVOIDANCE AND THE CATALAN TRIANGLE
#DEREK DESANTIS, REBECCA FIELD, WESLEY HOUGH, BRANT JONES, REBECCA MEISSEN, AND JACOB ZIEFLE


#From C5
#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: