Rotating an array using Juggling algorithm

How does the GCD decide the number of cycles needed to rotate the array?

Because the inner loop increments in steps of d, and stops when it gets back to the starting point, i.e. a total span which is some multiple of n. That multiple is LCM(n, d). Thus the number of elements in that cycle is LCM(n, d) / d. The total number of such cycles is n / (LCM(n, d) / d), which is equal to GCD(n, d).

Why is it that once we finish a cycle, we start the new cycle from the next element i.e. can't the next element be already a part of a processed cycle?

No. The inner loop increments in steps of d, which is a multiple of GCD(n, d). Thus by the time we start the i-th cycle, for a hit we'd need (k*GCD + z) % n == i (for 0 <= z < i). This leads to (k*GCD) % n == (i - z). This clearly has no solutions.


Little late to the party.

Though Oliver's answer explains it really well, I would also like to shade some more light on the details of his explanation.(might be useful to someone!)

How does the GCD decide the number of cycles needed to rotate the array?

let's find out why outer loop's length should be GCD(n,k) where n is the length of array and k is the shift. Let us assume length of outer loop should be x

In the juggling method of array rotation, inside the inner loop we basically swap the value of an array element j with value of another array element (j+k) mod n

arr[j] = arr[ (j+k) % n ]

so let's say for outer loop index i=0 we will have possible values for j as 0, (0+d) mod n, (0+2d) mod n, (0+3d) mod n..... (0+m*d) mod n where m is the smallest integer where (0+m*d) mod n becomes equal to i (as it's cyclic).

now the inner loop terminates when j's value becomes equal to i therefore,

 (0+m*d) mod n = i
 m*d mod n = 0

therefore m*d is the smallest number divisible by n and d both and by definition smallest number divisible by two numbers is called as LCM of those two numbers. so m*d = LCM(n, d). this is just one inner loop. so one inner loop runs about LCM(n, d) length (beware this is not runtime of inner loop but only the length it covers). so elements rotated by one loop will be LCM(n,d)/d as we are using d to jump to next index.

so, one loop covers LCM(n,d)/d Outer loops will run for x times and will cover all n elements of array therefore,

 x * LCM(n,d) / d  = n

we can simplify above equation and re-write it as below

 x = (n*d)  / LCM(n,d)

which is GCD(n,d). i.e. GCD can be calculated by dividing product of two numbers with their LCM.

 x = GCD(n,d).

Why is it that once we finish a cycle, we start the new cycle from the next element ie. can't the next element be already a part of a processed cycle?

You might have already observed that since we are jumping k units as a time in the inner loop once inner loop completes the first run length (LCM(n,d)) it's only going to repeat on the same indexes and not on different indexes. so the indexes which were not covered in the first run due to a certain starting position i will not be touched unless you change the i. (that's why outer loop changes the i). for e.g. Let's take an array A = [1,2,3,4,5,6] where n=6 and let's take d=2.

so if we trace the index j of inner loop for i=0 it will be j => 0, 2, 4, 0 and for i=1 it will be j = 1, 3, 5, 1

in this example GCD(6,2) was 2.

if we would have picked an array of length 5 and d=2 then the trace would have been j => 0, 2, 4, 1, 3, 0 and there would have only been one outer loop which also meets with GCD(5,2)= 1.


As per my understanding following implementation done for juggling algorithm, but what happens when length in 13 and rotation is 3 so GCD will become invalid, so splitting into the step also causes the problem.

follows juggling algorithm 

public void jugglingAlgorithm(int arr[],int limit)
{
    for(int i =0;i<findGCD(arr.length, limit);i++)//iterate the sets
    {
        int j;
        int temp = arr[i];
        for(j=i;j<arr.length;j = j+limit)
        {
            if((j+limit)>=arr.length) arr[j] = temp;
            else arr[j]=arr[j+limit];               
        }       
    }
    printArray(arr);
}


public int findGCD(int num1,int num2)
{
    int gcd = 1;
    for(int i=1;(i<=num1 && i<=num2);i++)
    {
        if(num1%i==0 && num2%i==0) gcd = i;
    }
    return gcd;
}

public void printArray(int[] arr){
    for(int i=0;i<arr.length;i++)
    {
        System.out.print(arr[i]+"\t");
    }
    System.out.println("");
}

GCD is really an example of the beauty of maths. Sometimes, when you get the thing in your mind, your mind would answer itself for the things it does putting how it happened aside.

Now coming to question, the rotation task, simply could have been worked with a for-loop. Juggling algorithm might have some advantages over it (I didn't find what).

Now coming to the point Why GCD. The GCD gives an exact figure of rotation to be performed. It actually minimizes no of rotations.

For example,

if you want to perform rotation of 30 numbers

with d = 1 the outer loop will be rotating once and inner would rotate 30 times 1*30=30

with d = 2 the outer loop will be rotating twice and inner would rotate 15 times 2*15=30

with d = 3 the outer loop will be rotating thrice and inner would rotate 10 times 3*10=30

So, the GCD Here would ensure the rotations don't exceed the value 30. And as you are getting a number that is divisor of total elements, It won't let skip any element

Tags:

Algorithm

Arrays

Recent Posts