Avoiding having to calculate the gcd when doing cycle decomposition -- Raymond Chen
Last time, we looked at how clang’s libcxx implementation of
std:: uses cycle decomposition to minimize the number of swaps. Doing so requires calculating the greatest common divisor, but I noted that the OpenJDK implementation of the java standard library uses a trick to avoid doing the gcd calculation.
Rotation revisited: Avoiding having to calculate the gcd when doing cycle decomposition
by Raymond Chen
From the article:
The trick is realizing that the total number of elements is equal to the sum of the lengths of each of its cycles, and each of the initial elements belongs to a different cycle. Therefore, we can just keep rotating elements until the number of elements rotated is equal to the total. We don’t have to precalculate the number of cycles; we just let the counter tell us when we’re done.
auto a = std::distance(first, mid); // number of "A" elements auto n = std::distance(first, last); // total elements auto count = 0; auto k = 0; while (count < n) { // Rotate the elements in the cycle starting at k auto save = std::move(first[k]); auto i, next = k; while (i = next, next = (i + a) % n, next != k) { first[i] = std::move(first[next]); ++count; } first[i] = std::move(save); ++count; }