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

while n=4 generates the lattice

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