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 AA' and BB'. 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(n2)O(n^2) time and uses O(m)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 nn times. Here, the minimum is 33. So we rotate the whole facet 33 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(n2)O(n^2) with O(1)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