Help:=proc() :print(`Rev(pi,i,j) , bp(pi), CleverS(pi) `):
print(`Neig(pi)`):
end:

#Rev(pi,i,j): the permutation obtained
#by reversing pi[i], ..., pi[j] and
#keeping the rest the same
Rev:=proc(pi,i,j)  local k:
[op(1..i-1,pi),
seq(pi[j-k],k=0..j-i),
op(j+1..nops(pi),pi)]

end:


#bp(pi): the number of "breakpoints" [non-adjacency] of pi
bp:=proc(pi) local c,pi1,i:
pi1:=[0,op(pi), nops(pi)+1]:

c:=0:

for i from 1 to nops(pi1)-1 do
 if  abs(pi1[i+1]-pi1[i])<>1 then
        c:=c+1:
 fi:
od:
c:
end:

#Neig(pi):All the permutations reachable from
#pi via one reversal
Neig:=proc(pi) local i,j:

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


#BestNeig(pi):The best permutation reachable from
#pi via one reversal (the smallest number of breakpoints)
BestNeig:=proc(pi) local i,champ,rec:
S:=Neig(pi):
champ:=S[1]: 
rec:=bp(champ[2]):

for i from 2 to nops(S) do
 if bp(S[i][2])<rec then
     champ:=S[i]:
      rec:=bp(S[i][2]):
 fi:
od:
champ:
end:


#CleverS(pi): the clever greedy argument
#pick the neighbor with the least number of breakpoint
CleverS:=proc(pi) local L,pi1,tem:
L:=[]:
pi1:=pi:

while bp(pi1)>0 do
tem:=BestNeig(pi1):

L:=[op(L),tem[1]]:
pi1:=tem[2]:
od:

L:
end: