Help:=proc(): print(` Flip(pi,i), Neis(pi), Shells(n) `): 
print(`adj1(pi), Children(P) , WLS(pi)`):
end:
with(combinat):

#Flip(pi,i): flips the i-th pancake
Flip:=proc(pi,i) local j:

[seq(pi[i-j+1],j=1..i),op(i+1..nops(pi),pi)]:
end:

#Neis(pi): all the immediate neighbors of perm. pi
Neis:=proc(pi) local i:

{ seq(Flip(pi,i),i=2..nops(pi))}:
end:

#Shells(n): inputs a pos. integer n and outputs
#a list whose i-th entry is the SET of
#perms. of [1,n] who need at least i flips
Shells:=proc(n) local L,i,S,s,suzan:
suzan:=[seq(i,i=1..n)]:
S:=Neis([seq(i,i=1..n)]):
L:=[]:
while S<>{} do
L:=[op(L),S]:
S:=`union`(seq(Neis(s), s in S)):
S:=S minus (`union`(op(L)) union {suzan}):
od:
L:
end:

#adj1(pi): the number of adjancies of pi
adj1:=proc(pi) local n,co,i:
n:=nops(pi):
co:=0:

for i from 1 to n-1 do
 if abs(pi[i+1]-pi[i])=1 then
    co:=co+1:
 fi:
od:

if pi[n]=n then
   co:=co+1:
fi:

co:

end:



#Children(P): all the paris permutations (followed by the
#flip-list where the flip occured of the perm. pi
#where the children are richer than the parent
#For example, the Children of
#[2,4,1,3] are {[[4,2,1,3],2], [[1,4,2,3],3]}
Children:=proc(P) local i,S,n,pi1,pi,L:
pi:=P[1]:
L:=P[2]:

S:={}:
n:=nops(pi):

for i from 2 to n do
pi1:=Flip(pi,i):

if adj1(pi1)>adj1(pi) then
 S:=S union {[pi1, [op(L),i   ] ]}:
fi:
od:
S:


end:

#WLS(pi): All the wasteless prefix sorting sequences
WLS:=proc(pi) local S,a,n,Snew,Sold:
Sold:={[pi,[]]}:
n:=nops(pi):
a:=adj1(pi):
Snew:={[pi,[]]}:

while Snew<>{} do
Sold:=Snew:
Snew:=`union`(seq(Children(s), s in Snew)):


od:
Sold:

end: