# Vector rotation

> Rotate me right round baby right round.

November 20, 2022 · 4 min read · https://yasint.dev/vector-rotation/
Tags: math, vectors

---

Today I stumbled across an interesting problem. The concern is that we should rotate a one-dimensional vector of $n$ element left by $d$ ($\Delta$) positions.

## Problem statement

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

![Vector Rotation](./rotation.png)

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

![Alternative Approaches](./alt-approaches.png)

> Programming languages like python have insanely fast and well-optimized slicing operations. So, instead of iterating, a naive slicing algorithm could be faster for smaller input sizes ([Eli Bendersky, 2008](https://eli.thegreenplace.net/)).

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

## Aha!

Yes, we can! Thanks to [Jon Bentley](https://engineering.lehigh.edu/dac/jon-bentley), in his [Programming Pearls (2nd edition)](https://tfetimes.com/wp-content/uploads/2015/04/programmingpearls2nd.pdf) 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 wil 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)$ time.

> **Bidirectional Iterator** is an iterator that can be both _incremented_ and _decremented_. The requirement that a bidirectional iterator can be decremented is the only thing that distinguishes bidirectional iterators from **forward iterators**[^1]. In this case, we are using two iterators called $i$ and $j$.

[^1]: A forward iterator is an iterator that corresponds to the usual intuitive notion of a linear sequence of values ([boost.org](https://www.boost.org/), 1999)

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 $3$. If we view it as two sub-vectors, we get $3$ and $5$ items long sub-vector: `[1,2,3]`-`[4,5,6,7,8]`.

![Sub-vectors](./sub-vectors.png)

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.

![Sub-vector A Swap](./subv-a-swap.png)

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.

![Sub-vector B Swap](./subv-b-swap.png)

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

![Final Reverse](./final-reverse.png)

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 $x$ and _bidirectional iterator_ positions $i$ and $j$ for swapping the indexes. Then, we loop $\sum_{i}^{j}$ until $i \lt j$ to swap $x_i$ and $x_j$, and consecutively we increment $i$ and decrement $j$ by one.

Then comes the real magic. Inside the `reverseRotate` function we invoke the `reverse` routine $3$ times. The first call is to get $A'$ (we start from $0$ for $i$, and $j$ is always $\lt\Delta$), and then the second call is to derive $B'$ (we start from $\Delta$ for $i$ and swap until $n-1$). At this point, we only need to reverse the entire array once from $0$ to $n - 1$ to obtain the rotated vector.

```go isWindow caption="This algorithm runs in guranteed O(n) time using constant space."
func reverse(x *[]int, i, j int) {
	for i < j {
		(*x)[i], (*x)[j] = (*x)[j], (*x)[i]
		i++
		j--
	}
}

func reverseRotate(x *[]int, delta int) {
	reverse(x, 0, delta-1)
	reverse(x, delta, len(*x)-1)
	reverse(x, 0, len(*x)-1)
}
```

This is an elegant way to solve the problem, especially considering one vector as a sum of two ([Prakhar Srivastav, 2014](https://prakhar.me/)). In [Aha! Algorithms Research Paper](https://dl.acm.org/doi/pdf/10.1145/358172.358176) Jon mentions that this reversal code is guaranteed _time_ and _space-efficient_ and is so short and so damn simple that it's pretty hard to get wrong.

It is precisely the code that [Brian Kernighan](https://en.wikipedia.org/wiki/Brian_Kernighan) & [Bill Plauger](https://en.wikipedia.org/wiki/P._J._Plauger) use in their [Software Tools book](https://seriouscomputerist.atariverse.com/media/pdf/book/Software%20Tools%20in%20Pascal.pdf)'s editor and also what [Ken Thompson](https://en.wikipedia.org/wiki/Ken_Thompson) used in his text editor [`ed`](https://en.wikipedia.org/wiki/Ed_(text_editor)) 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!

- Book - [Programming Pearls 2nd edition](https://tfetimes.com/wp-content/uploads/2015/04/ProgrammingPearls2nd.pdf)
- Paper - [Aha! Algorithms](https://dl.acm.org/doi/pdf/10.1145/358172.358176)
- [Prakhar Srivastav @ Google](https://prakhar.me/articles/the-string-rotation-problem/)
- [Eli Bendersky @ Google](https://eli.thegreenplace.net/2008/08/29/space-efficient-list-rotation)

Thanks a million for reading! until next time!