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 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
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.
Thanks all for your answers, it was fun!
I've now implemented the algorithm in my Forth compiler.