#OK to post homework
#Victoria Chayes, 2/7/21, Assignment 5

Help:=proc(): print(`PermuG(n), NoABC(n)`): end:
with(combinat):

#1 Read the description of the Johnnson-Trotter algorithm here (by Dennis and Dennis) and implemet it by writing a procedure PermuG(n) that 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 (swapping neighboring entries).

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 type(i, even) then
 pi1:=[op(1..(j-1),pi),n,op(j..nops(pi),pi)]:
else 
 pi1:=[op(1..(n-j),pi),n,op((n-j+1)..nops(pi),pi)]:
fi:
 L:=[op(L),pi1]:
od:
od:
L:
end:





#4 A permutation π of {1,...,n} contains the pattern 123 if there exists a triple 1 ≤ i1 < i2 < i3 ≤ n such that π[i1] < π[i2] < π[i3]. Write a procedure NoABC(n) That inputs a positive integer n and outputs the set of permutations AVOIDING the pattern 123. Find [seq(nops(NoABC(n)),n=1..8)] Is it in the OEIS? What is its A number?

NoABC:=proc(n) local S,Snew,i,j:
S:=permute(n):
Snew:=convert(S,set):
for i from 1 to nops(S) do
for j from 1 to n-2 do
  if S[i,j]<S[i,j+1] and S[i,j+1]<S[i,j+2] then
   Snew:=Snew minus {S[i]}:
   break:
  fi:
od:
od:
convert(Snew,list):
end:

#We test with
#[seq(nops(NoABC(n)),n=1..8)]
#              [1, 2, 5, 17, 70, 349, 2017, 13358]
#
#This sequence is A049774 on OEIS. 


###########################
### Programs From Class ###
###########################