## 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

- Start with {1,2,...,n} and {L,L,L,...,L},
- Determine the largest mobile integer k
- Move the largest one only in the next step following the direction of its arrow
- Flip the direction of all integers p in the list with p > k
- 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:**