Thursday, June 28, 2012

String rotation

Given a string of length N, rotate the string by K units. Eg. rotation of abcdef by 2 units will result in cdefab.

Solution approaches:-
1) Using a temp Array
2) 1 shift at a time 

3) Juggling algorithm - uses GCD(N,K) outer loop and inner loop till cycle is encountered
4) Gries algorithm - divide and conquer
5) Reversal algorithm - revert individual blocks and then revert the full string
 

Links:-
Source - http://www.cs.bell-labs.com/cm/cs/pearls/s02b.pdf
Solution - http://www.geeksforgeeks.org/archives/2398
Solution - http://www.geeksforgeeks.org/archives/2878
Solution - http://www.geeksforgeeks.org/archives/2838
Solution and Performance - http://www.drdobbs.com/article/print?articleId=232900395&siteSectionName=parallel
 

Juggling algorithm explanation:-
Taken from http://eli.thegreenplace.net/2008/08/29/space-efficient-list-rotation/

Now, are you asking yourself "Just when will the process come back to x[0], and how many elements will have been moved by that stage ?". So did I, and the answer turns out to be an exciting application of the greatest common divisor (GCD) function.

In the first iteration, the "juggling pointer" jumps i elements at a time and stops when it reaches 0. How many steps will this take ? Ignoring the modulo for a moment, To reach 0, the pointer must be a multiple of n, so 0 will be reached at an index that is a multiple of both i and n. The first such multiple, in fact.

The first multiple (also known as LCM – least common multiple) is easy to compute from the GCD.

The amount of steps is lcm(n, i) / i. This is n / gcd(n, i). Therefore, in each iteration, n / gcd(n, i) elements will be rotated. The next iteration will pick up at x[1], an keep hopping in steps of i from there, moving another n / gcd(n, i) elements. In special cases, like when n and i are coprime, the first iteration will run over all the elements in the vector, without the need for a second one.

In any case, the whole process will always make n steps in total, moving all the elements to their correct positions.

No comments: