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.

type Direction byte

const (
	up    Direction = iota
	right Direction = iota
	down  Direction = iota
	left  Direction = iota
)

func reverse[T any](x *[]T, i, j int) {
	for i < j {
		(*x)[i], (*x)[j] = (*x)[j], (*x)[i]
		i++
		j--
	}
}

func reverseRotate[T any](x *[]T, delta int, direction Direction) {
    if delta == len(*x) {
		return
	}
	switch direction {
	case left, up:
		reverse(x, 0, delta-1)
		reverse(x, delta, len(*x)-1)
	case right, down:
		reverse(x, len(*x)-delta, len(*x)-1)
		reverse(x, 0, len(*x)-delta-1)
	}
	reverse(x, 0, len(*x)-1)
}

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.

a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
reverseRotate(&a, 1, up)

// =>
// [9 8 7 6]
// [5 4 2 3]
// [8 7 3 4]
// [2 3 4 5]

Shift down

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

a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
reverseRotate(&a, 1, down)

// =>
// [8 7 3 4]
// [2 3 4 5]
// [9 8 7 6]
// [5 4 2 3]

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).

Not the Optimal Way — You’re advised to think through and use it because it’s not the optimal way to do it. Libraries like NumPy have clever optimizations for functions such as transpose, rot90, flip, etc. But in our problem, we intend to rotate each column. If you find a more efficient solution, let me know as well, haha.

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: -

func rotate2D[T any](x *[][]T, deltas []int, dir Direction) error {

	// the length of the changes must be exact.
	// if it's 6x6 then: deltas = {?, ?, ?, ?, ?, ?}
	if len(deltas) != len(*x) {
		return errors.New("columns are not equal")
	}

	// if every element in the deltas array is equal
	// then no point of rotating each column one by one.
	if EveryElementEquals(&deltas, &deltas[0]) {
		reverseRotate(x, len(deltas), dir)
		return nil
	}

	// try to reduce the column shifts.
	ReduceShifts(x, &deltas, dir)

	for ci, cn := range deltas {

		// if there's no rotations to be done
		// then, simply skip this column.
		if cn <= 0 {
			continue
		}

		// Extract the column elements.
		var col []T
		for _, row := range *x {
			col = append(col, row[ci])
		}

		// rotate the temporary column.
		reverseRotate(&col, cn, dir)

		// reassign the elements to correct
		// indices after shifting.
		for si, s := range col {
			(*x)[si][ci] = s
		}

	}

	return nil

}

func ReduceShifts[T any](x *[][]T, deltas *[]int, dir Direction) {

	// find the minimum delta value
	min := FindMinDelta(deltas)
	if min <= 0 {
		return
	}

	// do a minimum rotation
	reverseRotate(x, min, dir)

	// reduce the shifts by min value
	for i := range *deltas {
		if (*deltas)[i] == min {
			(*deltas)[i] = 0
		} else {
			(*deltas)[i] = (*deltas)[i] - min
		}
	}

}

func EveryElementEquals(a *[]int, x *int) bool {
	for i := 1; i < len(*a); i++ {
		if (*a)[i] != *x {
			return false
		}
	}
	return true
}

func FindMinDelta(x *[]int) int {
	smallest := (*x)[0]
	for _, num := range (*x)[1:] {
		if num < smallest {
			smallest = num
		}
	}
	return smallest
}

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!

m6x6 := [][]int{
	{0, 0, 0, 0, 0, 0},
	{1, 1, 1, 1, 1, 1},
	{2, 2, 2, 2, 2, 2},
	{3, 3, 3, 3, 3, 3},
	{4, 4, 4, 4, 4, 4},
	{5, 5, 5, 5, 5, 5},
}

deltas := []int{4, 5, 6, 6, 4, 3}

err := rotate2D(&m6x6, deltas, up)
if err != nil {
	panic(err)
}

// =>
// 4   5   0   0   4   3
// 5   0   1   1   5   4
// 0   1   2   2   0   5
// 1   2   3   3   1   0
// 2   3   4   4   2   1
// 3   4   5   5   3   2

Bonus: shift left and 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: -

a := [][]int{
	{2, 3, 4, 5},
	{9, 8, 7, 6},
	{5, 4, 2, 3},
	{8, 7, 3, 4},
}
for _, x := range a {
	reverseRotate(&x, 1, left)
    // reverseRotate(&x, 1, right)
}

// =>
// [3 4 5 2]
// [8 7 6 9]
// [4 2 3 5]
// [7 3 4 8]

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?I’ll show you how to do this efficiently without hogging up our precious CPU in an upcoming article. Reverse Rotate algorithm is an absolute gem.

That’s it folks!