[MS] Rotation revisited: Cycle decomposition in clang's libcxx - devamazonaws.blogspot.com
We got distracted by the rotation algorithm in gcc's libstdc++, but let's get back to the cycle decomposition algorithm in clang's libcxx . 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 for...