Background

I am reading "Introductory Combinatorics" by Brualdi. In Chapter 4, an algorithm is introduced to generate all permutations of a list of number $\{1,2,3,...,n\}$. In the case of four elements, according to the book, the order of permutation looks like the following:

Brualdi use an algorithm introduced mentioned by S. Even to implement the interlaced pattern:

I think it would fun to animate this process in Wolfram Language. Notice the how the numbers and arrow direction are updated:

Animation of 4 elements

Animation with 5 elements. Cure to insomnia

A notebook which contains all running code is attached. Please find it at the end of this thread.

Explanation

To implement this algorithm, we introduce

• Number-direction pair. For example 2 is with an arrow atop which pointing to the right ;1 is with an arrow atop which pointing to the left

  dirList={"R","R","R","L","R","R"};
  numList={2,6,3,1,5,4};
  

• Mobile Integer. In the list above, $6$, $3$ and $5$ are mobile integers because the arrow of each item points to a smaller number than itself. $6$ with "R", means $6$ looks toward right at $3$, and $6>3$. Apparently 2 is not a mobile integer since 2 is less 6 which is on the right side. So is not 1, which is never a mobile integer. 4 is not mobile integer because there is no element on the right hand side of itself. The following code checks whether kth item in a list is a mobile integer or not:

  mobileIntQ[numList_List,dirList_List,kth_Integer]:=With[{max=Length[numList],newposition=If[dirList[[kth]]=="R",kth+1,kth-1]},
      Which[
                 newposition>max || newposition==0,False,
                 numList[[kth]]> numList[[newposition]],True,
                 True,False 
       ]
  ] 
  (* Test *)
  In[310]:= Cases[Range[6],x_/;mobileIntQ[numList,dirList,x]]
  (*the 2nd, 3rd and 5th items are mobile integers*)
  Out[310]= {2,3,5}
  In[311]:= numList[[%]]
  Out[311]= {6,3,5}
  

The algorithm

1. Start with {1,2,...,n} and {L,L,L,...,L},
2. Determine the largest mobile integer k
3. Move the largest one only in the next step following the direction of its arrow
4. Flip the direction of all integers p in the list with p > k
5. Do the last four steps again and again. Terminate until no mobile integer is found in the list.

Here is a step-by-step implementation. Suppose we have 4 elements

    (*initialization*)
    itemsNum = 4;
    numList = range = Range[itemsNum];
    dirList = ConstantArray["L", itemsNum];
    (* define direction flip actions *)
    flipDir["L"] = "R";
    flipDir["R"] = "L";

find out if the nth item in the list is mobile/Pickout the largest

mobileIndex = Cases[range, x_ /; mobileIntQ[numList, dirList, x]]  (* => {2, 3, 4}*)
mobileInts = numList[[mobileIndex]] (* => {2, 3, 4} *)

Here we find k=4 at position 4th (right most of the number list)

target = SortBy[Thread[mobileInts -> mobileIndex], First] // Last (* => 4 -> 4*)

Move 4 to the left for one step or just swap the position of 3 and 4:

maxMobileInt = target[[1]];
pos = target[[2]];
next = If[dirList[[pos]] == "R", pos + 1, pos - 1];
dirList[[{pos, next}]] = dirList[[{next, pos}]];
numList[[{pos, next}]] = numList[[{next, pos}]];

By the third step, flip the items in the number list that are larger than k = 4 (since no item is larger than 4, the direction list seems untouched):

With[{flip = Cases[numList, x_ /; x > maxMobileInt]},
       If[flip != {},
           toBeFlipped = Position[numList, #][[1, 1]] & /@ flip;
           dirList[[toBeFlipped]] = flipDir /@ dirList[[toBeFlipped]];,
           Clear[toBeFlipped]]
 ]

Till now we finished the first move:

numList = {1,2,3,4} = > numList = {1,2,4,3} , dirList = {L, L, L, L} => {L, L, L, L} 

The non-trivial move is the following:

{4,1,2,3} = > {4,1,3,2} , {L, L, L, L} => {R, L, L, L} 
{4,1,3,2} = > {1,4,3,2} , {R, L, L, L} => {L, R, L, L} 

Notice when

numList={4,1,2,3};
mobileIndex=Cases[range,x_/;mobileIntQ[numList,dirList,x]] (* *)
(* {3,4} = third and fourth element in numList are mobile integer *)

the leading 4 in numList with L is no longer a mobile integer and the largest mobile integer in the updated numList is 3. At this moment toBeFlipped is, for the first time, assigned value 1, which is position of 4 in numList. Thus the direction list dirlist changes from {L,L,L,L} to {R,L,L,L}.

The next move is obvious because in {4,1,3,2} with {R, L, L, L} 4 is the largest mobile integer to move right-ward. Therefore we have a switching point of 4 on the interlaced path:

1,4,2,3
4,1,2,3
4,1,3,2
1,4,3,2

Once we learn how this transition point is achieved by the code above, the rest part of the interlace pattern follows naturally.

Attachments: