Generating the unique paths to convert an ascending #permutation into a descending permutation using only adjacent swaps

One way to transform the list [1,2,3] to [3,2,1] is

[1,2,3] -> [2,1,3] -> [2,3,1] -> [3,2,1]

swapping only items that appear next to each other in the list. An alternate way is

[1,2,3] -> [1,3,2] -> [3,1,2] -> [3,2,1]

There is only one way to convert the series [1,2] to [2,1] which is by swapping the one and two in the series. For the ascending list [1,2,3] one can initially swap either 12 -> 21 or 23 -> 32. Only allowing smaller digits to move to the right and larger digits to move to the right, these two options lead to two unique sequences of swaps

1 [1,2,3] -> [2,1,3] -> [2,3,1] -> [3,2,1]
2 [1,2,3] -> [1,3,2] -> [3,1,2] -> [3,2,1]

Since each digit must move past each other digit, all digit pairs must be swapped at some point in the series of moves. This implies that for the digits 1 to n, there must be \binom{n}{2} steps to go from an ascending sequence to a descending sequence of digits. So, a three digit list requires 3 steps, a four digit list requires 6 steps, etc.

The four digit list [1,2,3,4] can start with any of three swaps, 12->21, 23 -> 32, or 34 -> 43. This creates the 16 following paths:

1  [1,2,3,4] -> [2,1,3,4] -> [2,3,1,4] -> [3,2,1,4] -> [3,2,4,1] -> [3,4,2,1] -> [4,3,2,1]
2  [1,2,3,4] -> [2,1,3,4] -> [2,3,1,4] -> [2,3,4,1] -> [3,2,4,1] -> [3,4,2,1] -> [4,3,2,1]
3  [1,2,3,4] -> [2,1,3,4] -> [2,3,1,4] -> [2,3,4,1] -> [2,4,3,1] -> [4,2,3,1] -> [4,3,2,1]
4  [1,2,3,4] -> [2,1,3,4] -> [2,1,4,3] -> [2,4,1,3] -> [4,2,1,3] -> [4,2,3,1] -> [4,3,2,1]
5  [1,2,3,4] -> [2,1,3,4] -> [2,1,4,3] -> [2,4,1,3] -> [2,4,3,1] -> [4,2,3,1] -> [4,3,2,1]
6  [1,2,3,4] -> [1,3,2,4] -> [3,1,2,4] -> [3,2,1,4] -> [3,2,4,1] -> [3,4,2,1] -> [4,3,2,1]
7  [1,2,3,4] -> [1,3,2,4] -> [3,1,2,4] -> [3,1,4,2] -> [3,4,1,2] -> [4,3,1,2] -> [4,3,2,1]
8  [1,2,3,4] -> [1,3,2,4] -> [3,1,2,4] -> [3,1,4,2] -> [3,4,1,2] -> [3,4,2,1] -> [4,3,2,1]
9  [1,2,3,4] -> [1,3,2,4] -> [1,3,4,2] -> [3,1,4,2] -> [3,4,1,2] -> [4,3,1,2] -> [4,3,2,1]
10 [1,2,3,4] -> [1,3,2,4] -> [1,3,4,2] -> [3,1,4,2] -> [3,4,1,2] -> [3,4,2,1] -> [4,3,2,1]
11 [1,2,3,4] -> [1,3,2,4] -> [1,3,4,2] -> [1,4,3,2] -> [4,1,3,2] -> [4,3,1,2] -> [4,3,2,1]
12 [1,2,3,4] -> [1,2,4,3] -> [2,1,4,3] -> [2,4,1,3] -> [4,2,1,3] -> [4,2,3,1] -> [4,3,2,1]
13 [1,2,3,4] -> [1,2,4,3] -> [2,1,4,3] -> [2,4,1,3] -> [2,4,3,1] -> [4,2,3,1] -> [4,3,2,1]
14 [1,2,3,4] -> [1,2,4,3] -> [1,4,2,3] -> [4,1,2,3] -> [4,2,1,3] -> [4,2,3,1] -> [4,3,2,1]
15 [1,2,3,4] -> [1,2,4,3] -> [1,4,2,3] -> [4,1,2,3] -> [4,1,3,2] -> [4,3,1,2] -> [4,3,2,1]
16 [1,2,3,4] -> [1,2,4,3] -> [1,4,2,3] -> [1,4,3,2] -> [4,1,3,2] -> [4,3,1,2] -> [4,3,2,1]

One can also view these paths as links in a lattice. For n=3, the lattice is

transitionLattice3

while n=4 generates the lattice

transitionLattice4

The following R code generates the unique sequences

# nextS returns an array with columns 1.sequence 2.pointer to the location of the swap 3.4. the digits swapped
# example: nextS(sstart <- 1:4, NULL, NULL)
nextS <- function(s, history, h) {
    n <- length(s)
    for (p in 2:n) {
        if (s[p-1] < s[p]) {
            s1 <- s
            s1[p-1] <- s[p]
            s1[p] <- s[p-1]
            h <- nextS(s1, rbind(history, c(p-1,s[p-1],s[p])),h)
        }
    }
    if (!is.null(history)) {
        if (nrow(history) == n * (n - 1) / 2) {
            if (is.null(h)) {
                hp <- 1
            } else {
                hp <- max(h[,1]) + 1
            }
        h <- rbind(h,cbind(hp, history))
        }
    }
    return (h)
}

 


The R code below displays the sequences

# display step-by-step swaps for each sequence
oneH2String <- function(h) return (paste('[',paste(h, collapse=','),']', sep=''))
    
h2String <- function(sstart, h) {
    scurrent <- sstart
    sequence <- oneH2String(scurrent)
    for (j in 1:nrow(h)) {
        stemp <- scurrent[h[j,1]]
        scurrent[h[j,1]] <- scurrent[h[j,1]+1]
        scurrent[h[j,1]+1] <- stemp
        sequence <- c(sequence, oneH2String(scurrent))
    }
    return (sequence)
}

 


hall <- nextS(sstart <- 1:4, NULL, NULL)
seqs <- sapply(1:max(hall[,1]), function(i) h2String(sstart, hall[hall[,1] == i,2:4]) )
data.frame(n=1:ncol(seqs), t(seqs))

 

The function can also be used to count the number of paths as a function of the length of the sequence. However, this number explodes for even short lists as shown in the following table (this appears to be the same sequence in The Online Encyclopedia of Integer Sequences)

list length number of paths
2 1
3 2
4 16
5 784
6 292,864
7 1,100,742,656
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: