There are several ways to deal with string rotation.
"Programming Pearls" talks about string rotation in deep, with three linear algorithms.(click here to check it)
The first one is called "Juggling algorithm", which I spent a lot time to study it, but I still can't understand the role that Great Common Divisor plays in it. Can anybody explain it in detail ?
You rotate the elements by moving them in steps of d. This process loops back after a certain number of moves, so that you need to apply m cycles of length l=n/m in total.
l is the first value that solves the equation l.d = 0 (mod n), so that m is precisely gcd(n, d).
Example 1: for n=12, d=3, 3 cycles of length 4:
0 3 6 9
1 4 7 10
2 5 8 11
Example 2: for n=12, d=10, 2 cycles of length 6:
0 10 8 6 4 2
1 11 9 7 5 3
(1 2 ... n). A theorem that states that the dth power of this permutation can be decomposed into gcd(d, n) disjoint cycles.thanks for your explanation! However, it was not very intuitive to me that you can jump to the conclusion
m=gcd(n,d)
, so I just want to share my reasoning here:
Since you want to find the smallest value such that
((n/m)*d)%n == 0, it means u want to find the biggest m that can satisfy this requirement. Starting from m = n, u can try it one by one and find out that when m=gcd(n,d) the equation is fulfilled. This is because: (n/m)*d = (n/m)*((d/m)*m) = n*(d/m). We need to ensure that d/m as well as n/m are both valid integers, and for the maximum such m, it must be the case that m=gcd(n,d).
nand the distancedare co-prime, the cgd is 1. You swap the elements in the order (0, 3, 6, 1, 4, 7, 2, 5) - all elements have been visited. If yourdis 4, the gcd is 4, too, and you swap only (0, 4) in the first cycle and you have to do that cycle again with offsets of 1, 2 and 3. In short: There are two nested loops. The product of the loop lengths must be yournand the inner loop length depends on the divisibility ofnbyd.