8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Not an answer, but an equivalent rephrasing of this problem is trying to get from a permutation of $\{1,2,..,n\}$ to "1 2 3 ... n" where the allowed moves are: take the leftmost element and insert it at a different position. So "4 1 3 2" could become "1 3 2 4", "3 1 2 4", then "1 2 3 4". Perhaps the optimal strategy will be easier to describe this way. $\endgroup$ – Matthew C Dec 2 '19 at 17:36
  • $\begingroup$ Thanks, I did think of somehow combining both strategies. So go forward with a non-optimal sequence and then somehow backtrack to the optimal one. But not even sure where I would start with that. $\endgroup$ – Guillermo Phillips Dec 2 '19 at 18:00
  • $\begingroup$ From your descriptions it seems to me that rotations can be applied only in one direction (i.e., the Nth element been removed and put at the top of the stack), right? so that it is not possible to move back the element in the top of the stack to the Nth position backwards. Am I correct? $\endgroup$ – Carlos Linares López Dec 3 '19 at 11:44
  • $\begingroup$ That's correct. But see answer. $\endgroup$ – Guillermo Phillips Dec 3 '19 at 11:57
6
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Nice analysis. With your order-statistic tree suggestion, this is just $O(n \log n)$. $\endgroup$ – j_random_hacker Dec 2 '19 at 23:50
  • $\begingroup$ Yes and I should mention that one could simplify things by moving the left side elements into the right side, insertion sort-style, which would be $O(n^2)$ average $\endgroup$ – Matthew C Dec 2 '19 at 23:52
  • $\begingroup$ Great, it seems good. Let me write the program/algorithm and I'll report back on the results. $\endgroup$ – Guillermo Phillips Dec 3 '19 at 10:39
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks a lot for posting your own implementation! One question though, what is the expected size of your permutations? $\endgroup$ – Carlos Linares López Dec 3 '19 at 15:50
  • 1
    $\begingroup$ In my Forth implementation probably not more than four. So it's probably overkill for my needs. But if your permutations are going to be very large, then using some kind of fast insertion algorithm (as suggested by the other answer), will improve performance - otherwise performance will be O(n^2). $\endgroup$ – Guillermo Phillips Dec 3 '19 at 15:54
  • $\begingroup$ I do find it amazing that this problem could be optimally solved for permutations of arbitrary size in polynomial time. There are a good number of permutation problems like this and they are all exponentially hard. Certainly, not all have to be exponentially hard ... I was considering to post an answer based on IDA* and the gap heuristic for your specific problem ... $\endgroup$ – Carlos Linares López Dec 3 '19 at 15:59
  • 1
    $\begingroup$ If you have a different solution, then please do post it. It's always good to see a problem from more than one angle. I must admit I was a little sceptical that it would return optimal solutions every time, but the logic makes sense and I've tested up to size 5 and all seems good. $\endgroup$ – Guillermo Phillips Dec 3 '19 at 16:26
  • $\begingroup$ Okay, let us see if I can allocate some spare time to do it ... I'm truly curious and I would like to compare both implementations $\endgroup$ – Carlos Linares López Dec 3 '19 at 16:32
1
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for your answer. It's the other way around. I would want to permute from 1234567 to 5362741 by moving elements to the top. Or inversely, sort 5362741 to 1234567 by repeatedly moving the top element to a position down the stack. $\endgroup$ – Guillermo Phillips Dec 3 '19 at 21:28
  • $\begingroup$ I get your point. Although, I suppose there would be a step to inverse the permutation before applying @Hendrik Jan's algorithm. $\endgroup$ – Guillermo Phillips Dec 3 '19 at 21:47
  • $\begingroup$ So that I understand, what would happen in the case of sorting 6274531? $\endgroup$ – Guillermo Phillips Dec 3 '19 at 21:52
  • 1
    $\begingroup$ 6 and 7 would be the unmoved ones; you would select 5, then 4, ..., then 1, to put on the left end. $\endgroup$ – Matthew C Dec 3 '19 at 22:06
  • 1
    $\begingroup$ @HendrikJan The data structure was to obtain the actual sequence of indices (representing which moves to perform). So that would correspond in your example to identifying the location of "4" so you can send it to the front; then identifying the location of "3" which has now changed, etc. I think to calculate and update those locations efficiently you need some kind of data structure. $\endgroup$ – Matthew C Dec 4 '19 at 16:00
1
$\begingroup$

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,

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I don't quite understand how this works; it shouldn't be possible to beat $O(n\log n)$, right? Otherwise this would be the default sorting algorithm (at least for sets of distinct elements) $\endgroup$ – Matthew C Dec 3 '19 at 20:47
  • $\begingroup$ Unless I missed some piece of information, this problem is easier to solve than the standard sorting algorithm. It also seems to me that Hendrik Jan's solution suggests solving it in O(n) rotating those positions that are inverted from large to small. The key observation here is that each rotation preserves the order of all symbols but the one that gets placed in the first position. Thus, from the larger symbol (9 in my example) down to the smaller (1 actually, zero does not need to be considered), rotate the symbol under consideration only if it is inverted $\endgroup$ – Carlos Linares López Dec 3 '19 at 21:32
  • $\begingroup$ Plugging your starting permutation 2764935801 into my VBA program only requires 8 rotates (86597899). You can see this immediately because the rightmost inversion (8,0) is in the eighth position. $\endgroup$ – Guillermo Phillips Dec 4 '19 at 11:08
  • $\begingroup$ @GuillermoPhillips Hey, thanks for your reply! I actually did not notice that you replied to me. What is the meaning of the digits of your solution? Are the positions or contents to rotate? I tried several forms to apply your solution but none worked. I realized, by the way, that my algorithm does NOT run in O(n) as I said because in every iteration the inverse of the permutation has to be updated but anyway I'm truly curious much the same $\endgroup$ – Carlos Linares López Dec 5 '19 at 20:22
  • $\begingroup$ @CarlosLinaresLópez each digit in 86597899, is the length of each rotate (-1) - or alternatively the position of the element (starting from zero), to bring to the top of the stack. It tells you how to permute 0123456789 to get to 2764935801 - which was my original question. My main point is that it only takes 8 rotates. $\endgroup$ – Guillermo Phillips Dec 6 '19 at 11:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.