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: ...
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 ...
Thanks to user111398. Here is some (Excel) VBA code to prove it works:
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)
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 ...
Let's suppose the input array is $A = [3,1,4,5,2]$. When sorting this array using pancake sorting, only flips of prefixes of the array are allowed. Flipping the first four elements, i.e. replacing $3145$ by $5413$, gives $A = [5,4,1,3,2]$. Then, flipping all five elements gives $[2,3,1,4,5]$, which brings the largest element to its correct position. By ...
We need to find the minimum number of transpositions that take one string $a$ to another string $b$, where $a, b$ are permutations. It looks like you are looking for the minimum distance between two given vertices $a, b \in S_n$ in the complete transposition graph, which is the Cayley graph of $S_n$ generated by the set of all transpositions.
Here's a python program that does this for $n=4$. In the $i$th iteration, each vector of length $i$ is appended with one of three possible strings to create vectors of length $i+1$.
n = 4
res = [["e1.1"], ["e1.2"], ["e1.3"]]
for i in range(2, n+1):
temp = res[:] #make a copy of current list
res = 
for x in temp:
res.append(x + ["e" +...