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:
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. 864
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. 242