Stack Permutation Algorithm

I was recently designing a Forth stack machine. I have an atomic instruction which rotates the top N elements.

For example if the top of the stack is on the left, then say the N=3 rotate instruction would do the following:

A B C D -> C A B D

A few more examples:

A B C D -> B A C D (N=2)
A B C D -> D A B C (N=4)

In other words the Nth element is removed and put at the top of the stack.

The question arises where I need to be able to permute the top N stack elements, but using the minimum number of rotate instructions.

How do I find the optimal sequence of rotations to perform for any given permutation?

A naive algorithm would be the following:

• Starting with the largest rotation (N=4 above), keep applying until the required element is in the 4th position.

• Reduce the size of the rotation by one and apply 1) again.

An example of the naive algorithm would be:

Permute: A B C D -> D A C B

If we list the rotate instructions in order as a list of numbers, would give:

4 4 3 3

But in fact, the optimal rotates would be:

3 2 4

EDIT - Further Investigations

I thought I would initially just try to enumerate all the optimal sequences for a given size of permutation - i.e. brute force it. And then look for patterns.

Here is the list I generated for size 4. I've renumbered the stack elements starting from zero, as that is actually more natural (since the top stack element is never moved to the top). So a 1 operation would bring the secondmost element to the top etc.:

-   ABCD
1   BACD
12  CBAD
123 DCBA
13  DBAC
133 CDBA
2   CABD
21  ACBD
213 DACB
22  BCAD
223 DBCA
23  DCAB
232 ADCB
233 BDCA
3   DABC
31  ADBC
312 BADC
313 CADB
32  BDAC
322 ABDC
323 CBDA
33  CDAB
332 ACDB
333 BCDA

A few observations are immediately apparent:

• The maximum number of operations needed is N-1 for a permuation of

size N.

• There are more optimal sequences starting with 3 than with 2,

and more with 2 than with 1.

• There is a regula

Ok here's my attempt 2 which won't construct the sequence of moves, but it at least proves what the optimal number of moves is and gives an indicator of how to construct the sequence. I'm addressing the inverse problem of turning "σ(1)σ(2)…σ(n)" to "12…n" using the moves "insert the current leftmost element somewhere different in the array", but they are equivalent problems because if we choose a prefix $\sigma(1)\sigma(2)\ldots \sigma(i)$ and right-cycle it, then we can reverse that by choosing the $\sigma(i)$ (now the leftmost point) and inserting it at position $i$. Likewise rather than start from the identity, we end at the identity.

Let $\sigma(i^)$ be the right most element that is the beginning of an inversion, i.e., there exists $j>i^$ with $\sigma(i^*)>\sigma(j)$ (if none exists then no moves are necessary because $\sigma$ is the identity permutation). For instance in 1 3 2 4 that would be 3 since it starts the inversion (3,2). And in 4 3 2 1 that would be 2.

Observation 1: $\sigma(i^+1)\sigma(i^+2)\cdots \sigma(n)$ is sorted.

We must move all elements on the left side of $\sigma(i^)$ to the right side of $\sigma(i^)$. This is because we must correct the inversion and that can't happen until we perform a move with $\sigma(i^)$ itself, which can't happen until $\sigma(i^)$ is "uncovered" on the left side. While performing these hops over $\sigma(i^)$ we can maintain the invariant that everything to the right of $\sigma(i^)$ is sorted; this is just insertion into a sorted array.

So the number of moves necessary $= i^$, since we hop everything to the left of $\sigma(i^)$, and lastly move $\sigma(i^*)$ to its correct index.

Concluding note: to actually find the indices, we could use an order-statistic tree initialized with all values to the right of $\sigma(i^)$. When we jump $\sigma(1)$ over $\sigma(i^)$ we insert $\sigma(1)$ into the tree and call rank($\sigma(1)$); the rank can be used to compute the insertion index. Repeat with $\sigma(2), \ldots$.

StackExchange Computer Science Q#117949, answer score: 6