Message Boards Message Boards

GROUPS:

An Algorithm to Generate Permutation in Interlaced Pattern

Posted 1 year ago
1937 Views
|
1 Reply
|
4 Total Likes
|

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:

interlace

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

order

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

Animation with 5 elements. Cure to insomnia

5ele

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:

enter image description here - Congratulations! This post is now a Staff Pick as distinguished on your profile! Thank you, keep it coming!

Reply to this discussion
Community posts can be styled and formatted using the Markdown syntax.
Reply Preview
Attachments
Remove
or Discard

Group Abstract Group Abstract