Stack Permutation Algorithm

Question

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:

1. Starting with the largest rotation (N=4 above), keep applying until the required element is in the 4th position.
2. 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 regular pattern to the sequences starting in 1 or 3
• The longer sequences contain the shorter ones to the left hand side. In other words if 322 appears then so will 32 and 3.
• There is a unique optimal sequence for each permuation

The pattern seems to be the following for those starting with 3 for example:

3(123)(23) - where the brackets indicate a choice

or for 1

1(23)3

But the pattern is not so obvious for those starting with 2.

Still, all that doesn't help in finding the actual sequence for a permutation.

---

EDIT

Thanks all for your answers, it was fun!

I've now implemented the algorithm in my Forth compiler.

Answer 1

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

Answer 2

Thanks to user111398. Here is some (Excel) VBA code to prove it works:

Option Explicit

Public Sub Test()
    Dim sPermutation As String

    Dim lIndex As Long

    For lIndex = 0 To 2 * 3 * 4 * 5 - 1
        sPermutation = GetPermutation(lIndex, "ABCDE")
        Debug.Print sPermutation & ": " & GetRotates(sPermutation)
    Next

End Sub

Public Function GetPermutation(ByVal lPermutationIndex As Long, ByVal sPermute As String) As String
    Dim lIndeces() As Long
    Dim lIndex As Long
    Dim sPermutation As String

    ReDim lIndeces(Len(sPermute) - 1)
    For lIndex = 0 To UBound(lIndeces)
        lIndeces(lIndex) = lPermutationIndex Mod (lIndex + 1)
        lPermutationIndex = lPermutationIndex \ (lIndex + 1)
    Next

    For lIndex = 0 To UBound(lIndeces)
        sPermutation = Left$(sPermutation, lIndeces(lIndex)) & Mid$(sPermute, lIndex + 1, 1) & Mid$(sPermutation, lIndeces(lIndex) + 1)
    Next
    GetPermutation = sPermutation
End Function

Public Function GetRotates(ByVal sPermutation As String) As String
    Dim lIndex As Long
    Dim sMove As String
    Dim lFulcrum As Long

    ' Find rightmost inversion (fulcrum)
    For lIndex = Len(sPermutation) To 2 Step -1
        If Mid$(sPermutation, lIndex, 1) < Mid$(sPermutation, lIndex - 1, 1) Then
            lFulcrum = lIndex - 1
            Exit For
        End If
    Next

    ' No inversion then no rotates
    If lFulcrum = 0 Then
        GetRotates = "-"
        Exit Function
    End If

    ' Keep moving leftmost to the right of the inversion and keep sorted
    Do
        sMove = Left$(sPermutation, 1)
        For lIndex = lFulcrum + 1 To Len(sPermutation)
            If sMove < Mid$(sPermutation, lIndex, 1) Then
                sPermutation = Mid$(sPermutation, 2, lIndex - 2) & sMove & Mid$(sPermutation, lIndex)
                GetRotates = (lIndex - 2) & GetRotates
                lFulcrum = lFulcrum - 1
                Exit For
            End If
        Next
        If lIndex > Len(sPermutation) Then
            sPermutation = Mid$(sPermutation, 2) & sMove
            GetRotates = (Len(sPermutation) - 1) & GetRotates
            lFulcrum = lFulcrum - 1
        End If
    Loop Until lFulcrum = 0

End Function

Obviously you can convert the GetRotates function to use arrays and your own flavour of language.

Note that the output of GetRotates is zero based and is based on moving elements to the top of the stack.

As suggested in the accepted answer, an Order Statistic Tree can be used to improve the performance of the sorting to the right of the inversion.

Answer 3

As previously suggested we will discuss the inverse problem, sorting. If we want to sort 5 3 6 2 7 4 1 to 1 2 3 4 5 6 7 by moving elements to the left (top) the only way to get 7 to the bottom is to move 4 and 1 out of the way. Then to get 6 as second last element we also need to move 2. Then to get 5 at the right position we also need to move 3. Now that we know which numbers to move (1 to 4) we can easily find an optimal way to do that, just move these numbers to front from large to small.

Hence, in general, for a permutation of $1,\dots,n$ the numbers that do not have to be moved are the maximal sequence that is a subsequence $k,k+1, \dots n-2,n-1,n$ of the original permutation. All other numbers are moved, from large to small. The sequence is easily found, starting at the end.

In the first example, the subsequence is $5,6,7$ in $\underline 5,3,\underline 6,2,\underline 7,4,1$

Answer 4

This is only an attempt to provide another implementation that solves the nth stack sorting problem (I had to give it a name, ...) with permutations of an arbitrary size $n$ in $O(n)$ ---though the implementation given below works only for digits in the range $[0, n)$.

Actually, the analysis provided by user111398 is very nice and (s)he is absolutely right: to compute the optimal number of moves required to sort the permutation it just suffices counting the number of inversions, or locations $j>i$ with $\sigma(i)>\sigma(j)$. Indeed, the problem can be optimally solved in $O(n)$ just by undoing all inversions from the last symbol all the way down to the first one ---and, as a corollary the length of the optimal solution is actually bounded by $(n-1)$.

For this, there is no need to use an order-statistic tree, but just to compute the inverse of the permutation. The inverse $\pi^{-1}$ of a permutation $\pi$ records the location of each symbol, i.e., $\pi^{-1}[\pi[i]] = i$.

Thus, in the first iteration, if and only if $\pi^{-1}[n-1] < \pi^{-1}[n-2]$, then rotating all symbols up to the location of symbol $(n-2)$ undoes the inversion. Next, another rotation is practiced if and only if $\pi^{-1}[n-2] < \pi^{-1}[n-3]$ and so ... As each rotation only undoes one inversion, this number of rotations is the optimal number of moves required to sort the permutation.

#include <iostream>
#include <iterator>
#include <string>
#include <vector>

using namespace std;

// return the number of moves required to optimally solve the given
// permutation
int solve (vector<int>& perm)
{

  // compute the inverse permutation
  vector<int> inv (perm.size (), 0);
  for (auto i = 0 ; i < perm.size () ; inv[perm[i]] = i, i++);

  // process all symbols backwards but 0 which is necessarily well
  // placed in the last iteration
  int nbmoves = 0; // initialize the optimal number of moves required  
  int ith = perm.size () - 1;
  do {

    // if and only if the i-th symbol appears before the (i-1)-th
    // symbol
    if (inv[ith] < inv [ith-1]) {

      cout << "* [" << ith << "] ";
      copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
      cout << endl;

      // then rotate all symbols up to the location of the (ith-1)
      // symbol
      for (auto i = inv[ith-1] ; i > 0 ; perm[i]=perm[i-1], i--);
      perm[0]=ith-1;

      // increment the required number of moves
      nbmoves++;

      // and update the inverse
      for (auto i = 0 ; i < perm.size () ; inv[perm[i]] = i, i++);
    }
    else {
      cout << "  [" << ith << "] ";
      copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
      cout << endl;
    }

    // move to the next symbol
    ith--;
  } while (ith > 0);

  cout << "  "; 
  copy ( perm.begin(), perm.end(), ostream_iterator<int> (cout,", "));
  cout << endl;

  return nbmoves;
}

int main (int argc, char* argv[])
{

  // for all cases given in the command line
  for (auto i = 1 ; i < argc ; i++) {

    vector<int> perm;
    for (auto j = 0 ; argv[i][j] ; j++)
      perm.push_back (argv[i][j] - '0');
    int solution = solve (perm);
    cout << endl << " # moves required: " << solution << endl << endl;
  }
}

This implementation only accepts permutations with symbols in the range $[0, n)$:

$ ./stack_perm 2764935801
* [9] 2, 7, 6, 4, 9, 3, 5, 8, 0, 1, 
* [8] 8, 2, 7, 6, 4, 9, 3, 5, 0, 1, 
* [7] 7, 8, 2, 6, 4, 9, 3, 5, 0, 1, 
* [6] 6, 7, 8, 2, 4, 9, 3, 5, 0, 1, 
* [5] 5, 6, 7, 8, 2, 4, 9, 3, 0, 1, 
* [4] 4, 5, 6, 7, 8, 2, 9, 3, 0, 1, 
* [3] 3, 4, 5, 6, 7, 8, 2, 9, 0, 1, 
* [2] 2, 3, 4, 5, 6, 7, 8, 9, 0, 1, 
* [1] 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 
  0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 

 # moves required: 9

Hope this helps,