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: