By Yasin

Today I stumbled across an interesting problem which is a small sub-problem for a distributed algorithm I'm currently working on. The concern is that we should rotate a one-dimensional vector of nn element left by dd (Δ\Delta) positions.

Problem Statement

For instance, say we have an array with n=8n=8 elements should rotate it by d=3d=3 shifts. In example, vector [1,2,3,4,5,6,7,8] is rotated to [4,5,6,7,8,1,2,3].

A naive algorithm will use an n-element intermediate vector to do the job in nn steps or copy the underlying array with language dependant slicing features (where space is O(n)O(n)) or compute in-place shift by holding a temporary variable with dd iterations (which will take a running time of O(Δn)O(\Delta * n)).

But we are better than this! Can we rotate the vector in time proportional to O(n)O(n) without additional memory allocations O(1)O(1)?

Aha!

Yes, we can! Thanks to Jon Bentley, In his Programming Pearls (2nd Edition) book, he mentioned three vector rotation algorithms called Juggling, Swapping, and Reversing.

Jon derived a smart insight in which he calls the Aha! moment! Because, in the reverse rotation technique, it is basically two arrays reversed twice. Truly marvelous!

The reversing algorithm is pretty straightforward, and the other two are very clever. But for this code fragment, I will only go through the reversing algorithm because that's the most elegant code. Jon makes use of a bidirectional iterator to perform the task in O(n)O(n) time.

Now let's dive into the algorithm! Woohoo! 🕺

Reverse Rotate

Recall the example in the problem description. We have to left rotate the vector [1,2,3,4,5,6,7,8] by 33. If we view it as two sub-vectors, we get 33 and 55 items long sub-vector: [1,2,3]-[4,5,6,7,8].

In Jon's algorithm, to rotate the vector, we reverse the first sub-vector to obtain [3,2,1, 4,5,6,7,8]. Essentially, the first reverse of the Sub-vector A is swapping the positions of each element until delta.

Then reverse the second Sub-vector B to obtain [3,2,1, 8,7,6,5,4]. Like previously, we make use of the two-pointers to swap them in-place without additional space overhead.

Finally, reverse the whole thing to obtain [4,5,6,7,8,1,2,3].

That's it! How cool is that, huh?

Implementation

Here's a Golang implementation of this algorithm. The reverse function takes a pointer to the array xx and bidirectional iterator positions ii and jj for swapping the indexes. Then we loop ij\sum_{i}^{j} until i<ji \lt j to swap xix_i and xjx_j, and consecutively we increment ii and decrement jj by one.

Then comes the real magic. Inside the reverseRotate function we invoke the reverse routine 33 times. The first call is to get AA' (we start from 00 for ii, and jj is always <Δ\lt\Delta), and then the second call is to derive BB' (we start from Δ\Delta for ii and swap until n1n-1). At this point, we only need to reverse the entire array once from 00 to n1n - 1 to obtain the rotated vector.

Interactive Example

Here's a neat visual playground for you to see the behaviour of this algorithm!

This is an elegant way to solve the problem, especially considering one vector as a sum of two (Prakhar Srivastav, 2014). In Aha! Algorithms research paper Jon mentions that this reversal code is guaranteed time and space-efficient and is so short and damn simple that it's pretty hard to get wrong.

It is precisely the code that Brian Kernighan & Bill Plauger use in their Software Tools book's editor and also what Ken Thompson used in his text editor ed to manipulate lines.

Stay Curious

These are some interesting resources I referred while writing this post. Be sure to check these posts from great engineers out there!

Thanks a million for reading ! Until next time!

Published