with(combinat):
#Help2:=proc(): print(` redu(L), SubSeq3(L), Contain3(pi,sig)`): end:

#redu(L): inputs a list of distinct numbers and outputs its reduction
#according to their order
#For example redu([5,9,1]): [2,3,1]
#redu([Pi,e])=[2,1]
#
#redu([phi,sqrt(2),10])= [2,1,3]

redu:=proc(L) local n,L1,T,i:
n:=nops(L):
L1:=sort(L):
for i from 1 to n do
 T[L1[i]]:=i:
od:
[seq(T[L[i]],i=1..n)]:
end:

#SubSeqs3(L): The set of subsequences of the list L of length 3. For example
#SubSeqs3([1,6,2,4])={[1,6,2],[1,6,4],[1,2,4],[6,2,4]}
SubSeqs3:=proc(L) local n,i1,i2,i3,S:
n:=nops(L):
S:={}:
for i1 from 1 to n do
 for i2 from i1+1 to n do
   for i3 from i2+1 to n do
     S:=S union {[L[i1],L[i2],L[i3]]}:
   od:
od:
od:
S:
end:

#Contain3(pi,sig): does the permutation pi contain the pattern sig?
#Contain3([2,1,3,4],[1,2,3]) returns true Contain3([4,3,2,1],[1,2,3]) returns false
Contain3:=proc(pi,sig) local n,S,s:
n:=nops(pi):
if nops(sig)<>3 then
  RETURN(FAIL):
fi:

S:=SubSeqs3(pi):

for s in S do
  if redu(s)=sig then
     RETURN(true):
  fi:
od:
false:
end:


#AvoidPer1(n,sig): inputs a pos. integer n and a pattern of length 3 outputs the subset of permute(n)
#that avoid the parttern sig

AvoidPer1:=proc(n,sig) local A,pi,G:
A:=permute(n):
G:={}:
for pi in A do
 if not Contain3(pi,sig) then
  G:=G union {pi}:
 fi:
od:
G:
end: