An Algorithm to Generate Permutation in Interlaced Pattern

GROUPS:

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

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:
3 months ago
 - Congratulations! This post is now a Staff Pick as distinguished on your profile! Thank you, keep it coming!