All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars
 perplexus dot info

 Rotating an array (Posted on 2004-04-19)
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.

 See The Solution Submitted by e.g. Rating: 4.0000 (13 votes)

Comments: ( Back to comment list | You must be logged in to post comments.)
 Revised Algorithm | Comment 12 of 26 |
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

 Search: Search body:
Forums (0)