#OK to post homework
#George Spahn, 2/07/2021, Assignment 5

#PermuG(n): the list of all permutations of {1, ...,n} using johnson trotter
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]:
 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:=[op(1..n-j,pi),n,op(n+1-j..nops(pi),pi)]:
  fi:
  L:=[op(L),pi1]:
 od:
od:

L:
end:


#NextPG(pi), PrevPG(pi)


#MyRandPermA(n) Input a non-neg. integer n and outputs a random permutation 
# of {1,...,n} (uniformly at random) using
# The pre-pending paradigm, inspired by PermuA(n)

MyRandPermA:=proc(n) local S,j, J,pi:

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

S:=MyRandPermA(n-1):

j:= rand(1..n)():

J:=[seq(1..j-1), seq(j+1..n)]:

[ j, op(Expa(S,J)) ] :
end:

#MyRandPermI(n) Input a non-neg. integer n and outputs a random permutation 
# of {1,...,n} (uniformly at random) using
# The pre-pending paradigm, inspired by PermuA(n)

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

pi:=MyRandPermI(n-1):

j:= rand(1..n)():

[op(1..j-1,pi),n,op(j..nops(pi),pi)]:
end:


Avoids123:=proc(pi) local n,m1,m2,m3,i:
n:=nops(pi):
m1:=n:
m2:=n:
m3:=n:
for i from 1 to n do
if pi[i] < m1 then
 m1:=pi[i]:
fi:
if pi[i] < m2 and pi[i] > m1 then
 m2:=pi[i]:
fi:
if pi[i] > m2 then
 RETURN(false):
fi:
od:
RETURN(true):
end:


NoABC:=proc(n) local L,M,pi:
L:= []:
M:= PermuG(n):
for pi in M do
 if Avoids123(pi) then
  L:=[op(L),pi]:
 fi:
od:
L:
end:
#[seq(nops(NoABC(n)),n=1..8)] =

#[1, 2, 5, 14, 42, 132, 429, 1430]
#These are the Catalan numbers
#A000108


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