I have an array such as
ABCDEFGHIJK
I want to rotate it N places to the right; for example, if N=3, the array should end
IJKABCDEFGH
Assume that the only available operation is a FLIP method that can invert any portion of the array. For example, applied to the original array FLIP(3,6) would produce ABFEDCGHIJK.
Let M be the number of elements in the array, and N the displacement.
Algorithm: Compute, for each element in the array, its beginning and its final relative position number. Then, beginning with the leftmost letter (A), flip it with the letter holding its final relative position number. Then do that with the second, third, etc., until all the letters are in the offset sequence. At most M1 flips will be required, since they will give the first M1 letters their correct final relative position numbers, so that the Mth letter must then have its correct final relative position number too.
Edited on April 19, 2004, 7:57 pm

Posted by Penny
on 20040419 19:09:54 