Rotation revisited: Cycle decomposition in clang’s libcxx

https://devblogs.microsoft.com/oldnewthing/20260604-00/?p=112384">Rotation revisited: Cycle decomposition in clang’s libcxx

by Raymond Chen

From the article:

The implementation in clang’s libcxx performs the minimum number of swaps, roughly n/2, where n is the total number of elements. It does so by viewing the rotation as a permutation and walking through each of the cycles.

For notational convenience, let a be |A| and n be |A| + |B| (the total number of elements). The number of cycles is https://en.wikipedia.org/wiki/Greatest_common_divisor">gcd(a, b), and the k‘th cycle consists of the elements starting at first + k, and then stepping to the next element by moving forward another a elements, with wraparound, until you return back to the starting point.

For example, if you have |A| = 4 and |B| = 6, then the cycle that starts at A1 takes 4 steps forward to continues to B1; takes another 4 steps forward to B5; then takes 2 steps forward, wraps around, and then two more steps forward, landing on A3; then takes 4 steps forward to B3; and then takes 4 steps forward and wraps around to A1, which is the starting point.