So you want to rotate a vector, huh?

The solution I'm going to describe works well with both two-dimensional and multidimensional vectors if applied correctly. It is originally based on John Bentley's Reverse Rotate algorithm but with a teeny tiny twist. So, if you want to understand how this algorithm works, you have to read that article first.

All I did was invert the indices for left, up and right, down shift operations to achieve complement sub-vectors $A'$ and $B'$. This makes the algorithm more efficient and agile for dynamic programming.

Note that I have utilized generics in both functions to accept different types. [T any] allows multiple types as the argument (you may change this to any concrete type you desire). Additionally, we use an enumeration called Direction to improve the clarity of the code.

# Shift Up

Suppose you want to shift up all the 2D vector columns by 1.

# Shift Down

Suppose you want to shift down all the 2D vector columns by 1.

# Y-Axis Column Rotation

If you want to rotate specific columns with variable shifts. We need a bit more than reverseRotate. In such a case, the problem is a bit hard because when we think of it as columns, each element index is located in a different array. I devised a 3-step solution, which works for me right now (I want to keep it super simple).

For example, let's say we have a 3 x 3 matrix.

Here, the challenge is to shift columns 2 and 3 up by 1 and 2 consecutively instead of rotating the entire facet. Let's take a more complex input to understand how we can do it.

Suppose you have a 6 x 6 matrix.

And then, each column of the matrix has to be shifted up a variable amount of n.

We could do this in three easy steps. First, copying the target column to a temporary vector, then rotating it using reverseRotate, and finally reassigning the values for the source vector. However, this takes $O(n^2)$ time and uses $O(m)$ space to hold the temporary vector while iterating each column.

Here's the code for it: -

Also, note that ReduceShifts is a small optimization I've implemented for the algorithm. For example, if we receive the delta array [ 4,5,6,6,4,3 ], we can find the minimum delta and rotate the entire facet $n$ times. Here, the minimum is $3$. So we rotate the whole facet $3$ times. Once rotated, we can reduce the shifts of each delta by the minimum rotations we did, and we are left with new changes [1, 2, 3, 3, 1, 0]. Effectively reducing several iterations of the algorithm.

How to use this function, so? Simple!

# Bonus: Shift Left & Right

If you want to shift in the x-axis, then you have to iterate through each sub-vector of the 2D vector to achieve the outcome. For example, you could do the following: -

Left and right shifts yields a running time of $O(n^2)$ with $O(1)$ space in-place shifting. But why run sequentially, when you can parallelize 😎 *? Reverse Rotate algorithm is an absolute gem 💎.

That's it folks!

Published