I have an array such as
A-B-C-D-E-F-G-H-I-J-K
I want to rotate it N places to the right; for example, if N=3, the array should end
I-J-K-A-B-C-D-E-F-G-H
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 A-B-F-E-D-C-G-H-I-J-K.
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 M-1 flips will be required, since they will give the first M-1 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 2004-04-19 19:09:54 |
Revised Algorithm
