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