Help:=proc()
print(`N(pi), decompose(pi), find132Tree(pi), search_for_subtree(tree, i), find_descendants(tree), findIndecomposableTree(pi), findForest(pi)`):
end:

#redu(pi) finds the reduction of the given pattern
redu:=proc(pi)
RETURN(sort(sort(pi,'output=[permutation]'),'output=[permutation]')):
end:

#N(pi) computes the normalization of pi, i.e. the 132-avoiding permutation with the same left-to-right minima as pi.
N:=proc(pi) local ltrMinPositions, minVal, n, i, j, k, nonltr, filler, output, minElt:
ltrMinPositions:=[]:
minVal:=infinity:
n:=nops(pi):
for i from 1 to n do
 if pi[i]<minVal then
  ltrMinPositions:=[op(ltrMinPositions),i]:
  minVal:=pi[i]:
 fi:
od:
nonltr:={seq(i,i=1..n)} minus {op(ltrMinPositions)}:
filler:={seq(pi[i],i in nonltr)}:
output:=[]:
for i from 1 to n do
 if i in ltrMinPositions then
  output:=[op(output),pi[i]]:
 else
  j:=max({seq(k,k=1..i)} intersect {op(ltrMinPositions)}):
  minElt:=min({seq(k,k=pi[j]..n)} intersect filler):
  output:=[op(output),minElt]:
  filler:=filler minus {minElt}:
 fi:
od:
output:
end:

#decompose(pi) finds the decomposition of pi
decompose:=proc(pi) local output, largest, i,j,n, portion:
output:=[]:
n:=nops(pi):
i:=1:
largest:=n-1+min({op(pi)}):
while i <= n do
 portion:=[]:
 while true do
  portion:=[op(portion),pi[i]]:
  i:=i+1:
  if {op(portion)} = {seq(j,j=largest-nops(portion)+1 .. largest)} then
   output:=[op(output),portion]:
   largest:=largest - nops(portion):
   break:
  fi:
 od:
od:
output:
end:

#find132Tree(pi) finds the tree associated to the 132-avoiding permutation pi which ends with n
find132Tree:=proc(pi) local n,i,decomps:
#option remember:
n:=nops(pi):
if n = 1 then
 RETURN([pi[n],[]]):
fi:
decomps:=decompose([op(1..-2,pi)]):
RETURN([pi[n],[seq(find132Tree(decomps[i]),i=1..nops(decomps))]]):
end:

search_for_subtree:=proc(tree,i) local treepee,result:
if tree[1] = i then
 RETURN(tree):
fi:
if tree[2] = {} then
 RETURN(FAIL):
fi:
for treepee in tree[2] do
 result:=search_for_subtree(treepee,i):
 if result <> FAIL then
  RETURN(result):
 fi:
od:
RETURN(FAIL):
end:


find_descendants:=proc(tree) local output,subtree,treepee:
 output:={tree[1]}:
 subtree := tree[2]:
 for treepee in subtree do
  output:=output union find_descendants(treepee):
 od:
 RETURN(output):
end:
 

#findIndecomposableTree(pi) finds the labelled tree associated to the indecomposable 1342-avoiding permutation pi
findIndecomposableTree:=proc(pi) local norm,tree1,i,tree2,n,tree3,j,l,beaters,beatees,label,new_beaters,min_before,max_after,descendants,subtree,d,children_of_root,child:
n:=nops(pi):
norm:=N(pi):
tree1:=find132Tree(norm):
tree2:=subs({seq(norm[i]=[pi[i],l],i=1..n)},tree1):
tree3:=subs({seq(norm[i]=pi[i],i=1..n)},tree1):
for i from 1 to n-1 do
 subtree:=search_for_subtree(tree3,pi[i]):
 descendants:=find_descendants(subtree):
 beaters:={}:
 beatees:={seq(j,j=i+1..n)}:
 while beatees <> {} do
  new_beaters:={}:
  for d in {seq(j,j=2..n)} minus beaters do
   min_before:=min({seq(pi[j],j=1..d-1)}):
   max_after:=max({seq(pi[b], b in beatees)} intersect {seq(j,j=1..pi[d]-1)}):
   if min_before<max_after then
    new_beaters:= new_beaters union {d}:
   fi:
  od:
  beaters:=beaters union new_beaters:
  beatees:=new_beaters:
 od:
 label := nops(descendants intersect {seq(pi[b], b in beaters)}):
 tree2 := subs({[pi[i],l]=label},tree2):
od:
children_of_root:=tree2[2]:
label:=add(child[1],child in children_of_root):
tree2:=subs({[pi[n],l]=label},tree2):
RETURN(tree2):
end:

  
#getLtrMins(pi) returns the a list whose ith element is pi[i] if no previous element of pi is smaller than pi[i] and 0 otherwise
getLtrMins:=proc(pi) local n,minVal,output,i:
n:=nops(pi):
minVal:=infinity:
output:=[]:
for i from 1 to n do
 if pi[i] < minVal then
  minVal:=pi[i]:
  output:=[op(output),pi[i]]:
 else
  output:=[op(output),0]:
 fi:
od:
output:
end:

#getRtlMaxes(pi) returns the list whose ith element is pi[i] if no following element of pi is larger than pi[i] and 0 otherwise
getRtlMaxes:=proc(pi) local pip, inter,i,n:
n:=nops(pi):
pip:=[seq(n+1-pi[-i],i=1..n)]:
inter:=getLtrMins(pip):
RETURN(subs({n+1=0},[seq(n+1-inter[-i],i=1..n)])):
end:

findForest:=proc(pi) local perms,perm,forest:
perms:=decompose(pi):
forest:=[]:
for perm in perms do
 forest:=[op(forest),findIndecomposableTree(redu(perm))]:
od:
RETURN(forest):
end:

#node_count(tree) computes the number of nodes in a tree
node_count:=proc(tree) local i:
if tree[2] = [] then
 RETURN(1):
fi:
RETURN(1+add(node_count(tree[2][i]),i=1..nops(tree[2]))):
end:

#findPermutation132(tree) finds the indecomposable 132-avoiding permutation which would generate a given tree whose labels are all zeroes.
findPermutation132:=proc(tree) local m,nodes,output,level,i:
if tree[2] = [] then
 RETURN([1]):
fi:
m:=nops(tree[2]):
nodes:=[seq(node_count(tree[2][i]),i=1..m)]:
output:=[node_count(tree)]:
level:=0:
for i from m to 1 by -1 do
 output:=[op(findPermutation132(tree[2][i])+[level$nodes[i]]),op(output)]:
 level:=level+nodes[i]:
od:
RETURN(output):
end:

#deleteFirstLeaf(tree) inputs a tree and returns a tree with the leftmost leaf deleted
deleteFirstLeaf:=proc(tree) local i:
if tree[2] = [] then 
 RETURN():
fi:
if nops(tree[2]) = 1 then
 RETURN([tree[1],[deleteFirstLeaf(tree[2][1])]]):
fi:
RETURN([tree[1],[deleteFirstLeaf(tree[2][1]),seq(tree[2][i],i=2..nops(tree[2]))]]):
end:

#insertFirstLeaf(tree) inputs a tree and returns a tree with a new leaf inserted in the leftmost position.
insertFirstLeaf:=proc(tree) local i:
if tree[2] = [] then
 RETURN([tree[1],[[0,[]]]]):
fi:
if nops(tree[2]) = 1 then
 RETURN([tree[1],[insertFirstLeaf(tree[2][1])]]):
fi:
RETURN([tree[1],[insertFirstLeaf(tree[2][1]),seq(tree[2][i],i=2..nops(tree[2]))]]):
end:

#deleteFirstSubtree(tree,subtree) inputs a tree and a subtree; returns the tree with that subtree removed
deleteFirstSubtree:=proc(tree, subtree) local i:
if tree = subtree then
 RETURN():
fi:
if tree[2] = [] then
 RETURN(FAIL):
fi:
if nops(tree[2]) = 1 then
 RETURN([tree[1],[deleteFirstSubtree(tree[2][1],subtree)]]):
fi:
RETURN([tree[1],[deleteFirstSubtree(tree[2][1],subtree),seq(tree[2][i],i=2..nops(tree[2]))]]):
end:

#reduceEntries(tree) reduces all entries of ancestors of the first leaf by 1
reduceEntries:=proc(tree)
if tree = [1,[]] then
 RETURN([0,[]]):
fi:
if nops(tree[2]) = 1 then
 RETURN([tree[1]-1,[reduceEntries(tree[2][1])]]):
fi:
RETURN([tree[1]-1, [reduceEntries(tree[2][1]),seq(tree[2][i],i=2..nops(tree[2]))]]):
end:

#findPermutation(tree) finds the indecomposable permutation which would generate a given tree
findPermutation:=proc(tree) local first, first_leaf, first_parent, treepee, permpee, i, first_zero, treepoint, n, tree132, treevee, peevee, m, num_set1, num_set2, parent_point:
option remember:
n:=node_count(tree):
if not type(tree,'list') then
 RETURN():
fi:
#print(tree):
#print(n):
if tree=[0,[]] then
 RETURN([1]):
fi:
tree132:=findPermutation132(tree):
first := tree132[1]:
first_leaf:=tree:
while first_leaf[2] <> [] do
 first_parent:=first_leaf:
 first_leaf:=first_leaf[2][1]:
od:

#finds the tree when we are in the first two cases laid out in Combinatorics of Permutations 2nd Ed
if nops(first_parent[2]) >= 2 or first_parent[1] = 0 then
#print(`Case 1/2`):
 treepee:=deleteFirstLeaf(tree):
 permpee:=findPermutation(treepee):
 for i from 1 to nops(permpee) do
  if permpee[i] >= first then
   permpee[i] := permpee[i]+1:
  fi:
 od:
 RETURN([first, op(permpee)]):
fi:

#tests to see whether we are in the 3rd or 4th case laid out in Combinatorics of Permutations 2nd Ed
first_zero:=FAIL:
treepoint:=tree:
while treepoint[2] <> [] do
 if treepoint[1] = 0 then
  first_zero := treepoint:
 fi:
 treepoint:=treepoint[2][1]:
od:

#handles the third case laid out in ...
if first_zero <> FAIL then
#print(`Case 3`):
 treepee := insertFirstLeaf(deleteFirstSubtree(tree, first_zero)):
 permpee := redu(findPermutation(treepee)[2..-1]):
 treevee := first_zero:
# print(treepee):
 treevee[1] := add(first_zero[2][i][1], i=1..nops(first_zero[2])):
# print(treevee):
 peevee := findPermutation(treevee):
 m := node_count(treevee):
 num_set1 := sort([op(1..m, tree132)]):
 num_set2 := sort([op(m+1..-1, tree132)]):
 RETURN([seq(num_set1[peevee[i]],i=1..m),seq(num_set2[permpee[i]],i = 1..nops(permpee))]):
fi:

#handles the fourth case laid out in ... 
#print(`Case 4`):
#while treepoint[2][1][2] <> [] do
# treepoint[1] := treepoint[1]-1:
# parent_point := treepoint:
# treepoint := treepoint[2][1]:
#od:
#parent_point[2] := [treepoint[2][1]]:
treepee := deleteFirstLeaf(tree):
treepee := reduceEntries(treepee):
permpee := findPermutation(treepee):
RETURN([permpee[1],n,op(2..-1,permpee)]):

end:

#findPermutationFromForest(forest) finds the (possibly decomposible) permutation associated to a forest
findPermutationFromForest:=proc(forest) local tree,i,n,running_n,output,m,subperm,num_set:
n:=add(node_count(tree),tree in forest):
running_n:=n:
output:=[]:
for tree in forest do
 m:=node_count(tree):
 subperm:=findPermutation(tree):
 num_set:=[seq(i,i=running_n-m+1..running_n)]:
 running_n:=running_n-m:
 output:=[op(output),seq(num_set[subperm[i]],i=1..m)]:
od:
RETURN(output):
end: