By Blog Staff | Jul 27, 2026 01:29 PM | Tags: None

RaymondChen_5in-150x150.jpgWe got distracted by the rotation algorithm in gcc’s libstdc++, but let’s get back to the cycle decomposition algorithm in clang’s libcxx.

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