Rotating an array using Juggling algorithm

Question

I recently learnt about how the Juggling algorithm rotates an array in linear time when I was reading the solution in the Programming Pearls book.

The code to solve it was as follows:

/*Function to left rotate arr[] of siz n by d*/
void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  for (i = 0; i < gcd(d, n); i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

I have two questions regarding this algorithm -

1. How does the GCD decide the number of cycles needed to rotate the array?
2. 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?

I feel, I am missing something fundamental regarding the working of GCD, modulus and the cycles.

The following question had an answer to my first question, but still I was not able to understand it.

Juggling algorithm of string rotation

So, it would be helpful if someone can explain it in layman terms and the principle behind how they all gel together to make this algorithm work.

Answer 1

Here's a simpler solution that doesn't require you to calculate the GCD. You can compare the algorithm to drawing an N-pointed star in a circle.

public static void rotate(int[] array, int count) {
    if (count > 0) {
        int total = 0, start = 0, size = array.length;
        while (total < size) {
            int prevIndex = start;
            int prevValue = array[start];
            do {
                int nextIndex = (prevIndex + count) % size;
                int nextValue = array[nextIndex];
                array[nextIndex] = prevValue;
                prevValue = nextValue;
                prevIndex = nextIndex;
                total++;
            } while (prevIndex != start);
            start++;
        }
    }
}

Answer 2

Here is the Juggling Algorithm without using GCD in python. I provide it for completeness of those studying the problem. It counts characters moved and terminates when moved == n.

def rot_left(s, r : int):
    n = len(s)
    moved = 0
    i = 0

    # loop until n characters have been moved
    while (True):

        assert(moved < n)

        t = s[i]
        j = i # process the i'th stripe

        while (True):
            k = j + r
            if (k >= n):
                k -= n
            if (k == i):
                break # exit the inner loop when k has cycled back to i
            print('j =', j, 'k =', k)
            s[j] = s[k]; moved += 1
            j = k
        
        s[j] = t; moved += 1

        if (moved == n):
            break # exit the outer loop when n elements have been moved
        else:
            i += 1

    print('total moved =', moved, 'answer = ', "".join(s))


if (__name__ == '__main__'):

    s = list("abcdefg")
    rot_left(s, 3)

    s = list("abcd")
    rot_left(s, 2)

    s = list("abcdefghijklmnopqrstu")
    rot_left(s, 7)

This approach is suggested by the Programming Pearls text description after describing the inner loop - "If that process didn't move all the elements, then we start over at x[i] and continue until we move all the elements." - page 14, 3rd paragraph of the 2nd edition.

When the GCD is 1, a single pass processes all elements. When it is > 1, multiple passes (stripes) are necessary but each only moves n/GCD elements each - the work done is therefore always O(n) whether 1 or many passes are made.

Answer 3

The reasoning about why Juggling Algorithm works is not straightforward and is based on Modular Arithmetic. Below is a very brief informal outline:

1. For any positive integers a and n, say g=gcd(a,n) and t=n/g. Then, the numbers of the form (ai)mod n, i = 0,1,2,..,t-1 are all distinct and form the set G = {0,g,2g,...,(n/g-1)g}. (this itself requires a separate proof, you may refer the article linked below).

2. Further, for any integer b with 0 <= b < g, the numbers of the form (ai+b)mod n, i = 0,1,2,...,t-1 are all distinct and form the set G(b) = {b,g+b,2g+b,...,(n/g-1)g+b}.

3. It is easy to see that the sets G(0),G(1),...,G(g-1) have no element common between any two. Also, they together form the set of n elements: {0,1,2,...,n-1}.

4. The Juggling Algorithm (also known as Dolphin Algorithm) as described in the question, has integer a as d in above results. By iterating over i = 0,1,2,...,g-1, that program is effectively picking each of these g sets (for b=0,1,2,...,g-1) one by one. For each set, it moves each of its n/g elements to their final index.

For more details, you may like to refer below article (written by me):

https://mathsanew.com/articles/array_rotation_dolphin_algorithm.pdf

Answer 4

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.

Answer 5

Well I prefer this to do for array rotations where A is the array d is the rotations and n is the size of array:

For anticlockwise rotations:

def rotateArr(A,d,n):
A[:]=A[d:]+A[:d]
return A

Answer 6

If we understand the meaning of GCD and LCM we can relate why we used GCD for the juggling algorithm.

Gcd-> to equally distribute two or more sets of items into their largest possible grouping..

Lcm-> to figure out when something will happen again at the same time

Answer 7

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("");
}

Answer 8

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

Answer 9

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.