In-Place Array Rotations (Juggling/Reversal) & Matrix Transposition

Three-Reversal Involution vs. $\gcd(N, k)$ Juggling Cycles

Consider rotating an array $A = [X \;\vert\; Y]$ so that a prefix $X$ of length $n - k$ and a suffix $Y$ of length $k$ swap positions to become $Y X$ (a right rotation by $k \equiv k \bmod n$).In abstract algebra, reversing an array is an involution ($R(R(A)) = A$) that reverses the order of concatenated blocks: $(X Y)^R = Y^R X^R$. Therefore, reversing $X$ and $Y$ individually and then reversing the whole array (or reversing the whole array first, then reversing the first $k$ and last $n-k$ elements) yields:

$$\left( X^R Y^R \right)^R = (Y^R)^R (X^R)^R = Y X$$

Alternatively, consider Bentley's Juggling Algorithm: moving each element directly from index $i$ to $(i + k) \bmod n$ traces out cyclic orbits under the subgroup generated by $+k$ in $\mathbb{Z}_n$. By elementary group theory (Lagrange's theorem), the subgroup $\langle k \rangle \subseteq \mathbb{Z}_n$ has size $L = \frac{n}{\gcd(n, k)}$ and partitions the $n$ indices into exactly $g = \gcd(n, k)$ disjoint cycles, each of length $n / g$! Starting at each $s \in [0, g - 1]$ and chasing the cycle moves every element exactly once ($N$ writes vs. $3N$ reads/writes in 3-Reversal).

Comparison of In-Place Rotation & Transposition Algorithms

Visualizing 3-Reversal Rotation & $D_4$ Matrix Transpose + Reflect

Juggling Cycle Decomposition ($gcd(N, k)$ Orbits)

Production Implementation: 3-Reversal, Juggling & Cache-Tiled Square Transpose

#include <algorithm>
#include <cstdint>
#include <numeric>
#include <utility>
#include <vector>

// Cache-friendly 3-Reversal Right Rotation by k positions
template <typename T>
void rotate_right_reversal(std::vector<T>& a, std::size_t k) noexcept {
  const std::size_t n = a.size();
  if (n <= 1) return;
  k %= n;
  if (k == 0) return;

  std::reverse(a.begin(), a.end());
  std::reverse(a.begin(), a.begin() + static_cast<std::ptrdiff_t>(k));
  std::reverse(a.begin() + static_cast<std::ptrdiff_t>(k), a.end());
}

// Minimum-Move Juggling Left Rotation by k positions using gcd(n, k) cycles
template <typename T>
void rotate_left_juggling(std::vector<T>& a, std::size_t k) noexcept {
  const std::size_t n = a.size();
  if (n <= 1) return;
  k %= n;
  if (k == 0) return;

  const std::size_t cycles = std::gcd(n, k);
  for (std::size_t start = 0; start < cycles; ++start) {
    T tmp = std::move(a[start]);
    std::size_t cur = start;
    while (true) {
      std::size_t next = cur + k;
      if (next >= n) next -= n; // faster than % n!
      if (next == start) break;
      a[cur] = std::move(a[next]);
      cur = next;
    }
    a[cur] = std::move(tmp);
  }
}

// In-Place 90-Degree Clockwise Matrix Rotation (Cache-Tiled Transpose + Row Reverse)
void rotate_matrix_90_cw(std::vector<int>& mat, std::size_t n) noexcept {
  constexpr std::size_t TILE = 32;
  // Step 1: Tiled In-Place Transpose across upper triangle (r < c)
  for (std::size_t r0 = 0; r0 < n; r0 += TILE) {
    for (std::size_t c0 = r0; c0 < n; c0 += TILE) {
      const std::size_t r_end = std::min(r0 + TILE, n);
      const std::size_t c_end = std::min(c0 + TILE, n);
      for (std::size_t r = r0; r < r_end; ++r) {
        const std::size_t c_start = (r0 == c0) ? (r + 1) : c0;
        for (std::size_t c = c_start; c < c_end; ++c) {
          std::swap(mat[r * n + c], mat[c * n + r]);
        }
      }
    }
  }
  // Step 2: Reverse each row sequentially
  for (std::size_t r = 0; r < n; ++r) {
    auto row_begin = mat.begin() + static_cast<std::ptrdiff_t>(r * n);
    std::reverse(row_begin, row_begin + static_cast<std::ptrdiff_t>(n));
  }
}