Rotating elements in Array using Juggling/Dolphins Algorithm

Juggling/Dolphin’s algorithm is a technique used for array rotation, which is the process of shifting the elements of an array to the left or right by a certain number of positions. This algorithm is efficient and is particularly useful in situations where you need to perform frequent array rotations in-place without using any extra space. You may refer to this article to understand more about what array rotation means.

Array Rotation

Consider an array containing the following elements:

[1, 2, 3, 4, 5]

After rotating the elements by one position towards right, the array becomes:

[5, 1, 2, 3, 4]

Notice that all the elements moved by one position towards right. Also, the last element 5 wrapped around and moved to the starting of the array.

Similarly, after rotating the elements by one position towards right, the array becomes:

[4, 5, 1, 2, 3]

And so on..

Juggling/Dolphin’s Algorithm to Rotate Array

By now, you must have understood what an array rotation is and how positions of elements in an array are shifted. Let’s now take a look at the code to rotate an array by d positions towards right using Juggling/Dolphin’s algorithm:


def gcd(a, b):
  """Compute the greatest common divisor of a and b using the Euclidean algorithm."""
  if b == 0:
    return a
  else:
    return gcd(b, a % b)

def juggle_rotate(arr, d):
  """
  Rotate the array arr to the right by d positions using the juggling algorithm.
  
  Args:
  arr (list): The array to be rotated.
  d (int): The number of positions to rotate the array.
  """

  # If d is 0, no need to perform rotations
  if d == 0:
    return

  # Calculate the number of different sets/cycles we need to loop through
  num_cycles = gcd(len(arr), d)

  # Loop through each set and rotate all elements under it
  for cycle_start_idx in range(num_cycles):
    
    next_idx = cycle_start_idx
    running_num = arr[cycle_start_idx]
    
    # Rotate all elements present in the current set/cycle
    # Which starts from "cycle_start_idx"
    while True:
      # Calculate the next index in the current cycle
      next_idx = (next_idx + d) % len(arr)

      # Swap the current element with the running number
      running_num, arr[next_idx] = arr[next_idx], running_num

      # If we've come back to the starting index
      # It means all elements in the current set/cycle are rotated
      if next_idx == cycle_start_idx:
        break

# Lets now test the function
arr = [1, 2, 3, 4, 5, 6, 7, 8]
juggle_rotate(arr, 3)
print("Array after rotating all elements by 3 positions to the right: ")
print(arr)

arr = [1, 2, 3, 4, 5, 6, 7, 8]
juggle_rotate(arr, 4)
print("Array after rotating all elements by 4 positions to the right: ")
print(arr)


#include <stdio.h>

// Compute the greatest common divisor of a and b using the Euclidean algorithm
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

// Rotate the array arr to the right by d positions using the juggling algorithm
void juggle_rotate(int arr[], int n, int d) {
  // If d is 0, no need to perform rotations
  if (d == 0) {
    return;
  }

  // Calculate the number of different sets/cycles we need to loop through
  int num_cycles = gcd(n, d);

  // Loop through each set and rotate all elements under it
  for (int cycle_start_idx = 0; cycle_start_idx < num_cycles; cycle_start_idx++) {
    int next_idx = cycle_start_idx;
    int running_num = arr[cycle_start_idx];

    // Rotate all elements present in the current set/cycle
    // Which starts from "cycle_start_idx"
    while (1) {
      // Calculate the next index in the current cycle
      next_idx = (next_idx + d) % n;

      // Swap the current element with the running number
      int temp = arr[next_idx];
      arr[next_idx] = running_num;
      running_num = temp;

      // If we've come back to the starting index
      // It means all elements in the current set/cycle are rotated
      if (next_idx == cycle_start_idx) {
        break;
      }
    }
  }
}

int main() {
  int arr1[] = {1, 2, 3, 4, 5, 6, 7, 8};
  int n1 = sizeof(arr1) / sizeof(arr1[0]);
  juggle_rotate(arr1, n1, 3);
  printf("Array after rotating all elements by 3 positions to the right: ");
  for (int i = 0; i < n1; i++) {
    printf("%d ", arr1[i]);
  }
  printf("\n");

  int arr2[] = {1, 2, 3, 4, 5, 6, 7, 8};
  int n2 = sizeof(arr2) / sizeof(arr2[0]);
  juggle_rotate(arr2, n2, 4);
  printf("Array after rotating all elements by 4 positions to the right: ");
  for (int i = 0; i < n2; i++) {
    printf("%d ", arr2[i]);
  }
  printf("\n");

  return 0;
}


#include <iostream>
#include <vector>

// Compute the greatest common divisor of a and b using the Euclidean algorithm
int gcd(int a, int b) {
  if (b == 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

// Rotate the array arr to the right by d positions using the juggling algorithm
void juggle_rotate(std::vector<int>& arr, int d) {
  // If d is 0, no need to perform rotations
  if (d == 0) {
    return;
  }

  // Calculate the number of different sets/cycles we need to loop through
  int num_cycles = gcd(arr.size(), d);

  // Loop through each set and rotate all elements under it
  for (int cycle_start_idx = 0; cycle_start_idx < num_cycles; cycle_start_idx++) {
    int next_idx = cycle_start_idx;
    int running_num = arr[cycle_start_idx];

    // Rotate all elements present in the current set/cycle
    // Which starts from "cycle_start_idx"
    while (true) {
      // Calculate the next index in the current cycle
      next_idx = (next_idx + d) % arr.size();

      // Swap the current element with the running number
      std::swap(running_num, arr[next_idx]);

      // If we've come back to the starting index
      // It means all elements in the current set/cycle are rotated
      if (next_idx == cycle_start_idx) {
        break;
      }
    }
  }
}

int main() {
  // Test the function
  std::vector<int> arr = {1, 2, 3, 4, 5, 6, 7, 8};
  juggle_rotate(arr, 3);
  std::cout << "Array after rotating all elements by 3 positions to the right: ";
  for (int num : arr) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  arr = {1, 2, 3, 4, 5, 6, 7, 8};
  juggle_rotate(arr, 4);
  std::cout << "Array after rotating all elements by 4 positions to the right: ";
  for (int num : arr) {
    std::cout << num << " ";
  }
  std::cout << std::endl;

  return 0;
}


// Compute the greatest common divisor of a and b using the Euclidean algorithm
function gcd(a, b) {
  if (b === 0) {
    return a;
  } else {
    return gcd(b, a % b);
  }
}

// Rotate the array arr to the right by d positions using the juggling algorithm
function juggle_rotate(arr, d) {
  // If d is 0, no need to perform rotations
  if (d === 0) {
    return;
  }

  // Calculate the number of different sets/cycles we need to loop through
  const num_cycles = gcd(arr.length, d);

  // Loop through each set and rotate all elements under it
  for (let cycle_start_idx = 0; cycle_start_idx < num_cycles; cycle_start_idx++) {
    let next_idx = cycle_start_idx;
    let running_num = arr[cycle_start_idx];

    // Rotate all elements present in the current set/cycle
    // Which starts from "cycle_start_idx"
    while (true) {
      // Calculate the next index in the current cycle
      next_idx = (next_idx + d) % arr.length;

      // Swap the current element with the running number
      [arr[next_idx], running_num] = [running_num, arr[next_idx]];

      // If we've come back to the starting index
      // It means all elements in the current set/cycle are rotated
      if (next_idx === cycle_start_idx) {
        break;
      }
    }
  }
}

// Test the function
let arr = [1, 2, 3, 4, 5, 6, 7, 8];
juggle_rotate(arr, 3);
console.log("Array after rotating all elements by 3 positions to the right:");
console.log(arr);

arr = [1, 2, 3, 4, 5, 6, 7, 8];
juggle_rotate(arr, 4);
console.log("Array after rotating all elements by 4 positions to the right:");
console.log(arr);


import java.util.Arrays;

public class Main {
  // Compute the greatest common divisor of a and b using the Euclidean algorithm
  public static int gcd(int a, int b) {
    if (b == 0) {
      return a;
    } else {
      return gcd(b, a % b);
    }
  }

  // Rotate the array arr to the right by d positions using the juggling algorithm
  public static void juggle_rotate(int[] arr, int d) {
    // If d is 0, no need to perform rotations
    if (d == 0) {
      return;
    }

    // Calculate the number of different sets/cycles we need to loop through
    int num_cycles = gcd(arr.length, d);

    // Loop through each set and rotate all elements under it
    for (int cycle_start_idx = 0; cycle_start_idx < num_cycles; cycle_start_idx++) {
      int next_idx = cycle_start_idx;
      int running_num = arr[cycle_start_idx];

      // Rotate all elements present in the current set/cycle
      // Which starts from "cycle_start_idx"
      while (true) {
        // Calculate the next index in the current cycle
        next_idx = (next_idx + d) % arr.length;

        // Swap the current element with the running number
        int temp = arr[next_idx];
        arr[next_idx] = running_num;
        running_num = temp;

        // If we've come back to the starting index
        // It means all elements in the current set/cycle are rotated
        if (next_idx == cycle_start_idx) {
          break;
        }
      }
    }
  }

  public static void main(String[] args) {
    // Test the juggle_rotate function
    int[] arr = {1, 2, 3, 4, 5, 6, 7, 8};
    juggle_rotate(arr, 3);
    System.out.println("Array after rotating all elements by 3 positions to the right: ");
    System.out.println(Arrays.toString(arr));

    arr = new int[]{1, 2, 3, 4, 5, 6, 7, 8};
    juggle_rotate(arr, 4);
    System.out.println("Array after rotating all elements by 4 positions to the right: ");
    System.out.println(Arrays.toString(arr));
  }
}

Time Complexity:

The time complexity of the Juggling algorithm is O(n), where n is the length of the array. This is because the algorithm performs a series of swaps where each swap takes constant time, and the total number of swaps made is equal to the total number of elements present in the array.

Space Complexity:

The space complexity of the Juggling algorithm is O(1), which means it uses a constant amount of additional space. This is because the algorithm performs the rotations in-place, without requiring any additional data structures.

Idea behind the Algorithm

Let’s start with a simple scenario where we need to rotate the array: [1, 2, 3, 4, 5] by 3 positions to the right. Below is how the array looks after each rotation towards right:

[1, 2, 3, 4, 5] # Initial Array
[5, 1, 2, 3, 4] # After 1st rotation
[4, 5, 1, 2, 3] # After 2nd rotation
[3, 4, 5, 1, 2] # After 3rd rotation

If you observe closely,

The index of number 1 is 0 before rotation. After 3rd rotation, the index of number 1 is 3.
Similarly the index of number 2 is 1 before rotation. After 3rd rotation, the index of number 2 is 4
So we can generalize this as follows: If the index of an element is i before rotation, it’s position after rotating d positions towards right is i+d
So far so good, but for number 3, the index before rotation is 2. But after 3 rotations, the new index has to be “initial index + number of positions rotated” which is 2 + 3 = 5
But since the last index of the array is 4, we need to wrap this index and start again from the beginning. So you need to think of index 5 as the element after index 4 which is index 0 due to wrapping.
Mathematically, this can be computed as:
new_index = (old_index + positions_rotated) % array_len
For example, the old index of number 5 is 4. The new index after rotating 3 positions to the right will be (4 + 3)%5 which is 2.

The key idea behind Juggling/Dolphin’s algorithm is to start at the first element at index i and move it to i+d position. Now move the element originally present at i+d position to (i+d)+d position. We keep repeating this until we reach the first element. You can think of all elements covered in this loop to belong to a unique set.

In cases where the GCD of the length of the array and the number of rotations is 1 (i.e, there is no common divisor other than 1), there is only one set, and just one pass of the above algorithm is sufficient to rotate all elements. For example, in the below illustration with an array of 8 elements and 3 position rotation, we have only one cycle with sequence: 1 -> 4 -> 7 -> 2 -> 5 -> 8 -> 3 -> 6 -> 1. Juggling and rotating all elements in this sequence starting from element 1 will result in a rotated array.

But in cases where the GCD is more than 1, there are more than 1 sets/cycles and so we need to iterate through each set/cycle and rotate all elements present in each set/cycle. For example, in the below illustration with an array of 8 elements 2 position rotation, we have two cycles, one with sequence: 1 -> 3 -> 5 -> 7 -> 1 and the other with sequence 2 -> 4 -> 6 -> 8 -> 2. Juggling and rotating all elements present in both these cycles will result in a complete rotated array.

In the Juggling/Dolphin’s algorithm we went through, the first loop loops through the starting index of each set/cycle and the second loop rotates all elements present in that particular set.

References

Mathematical proof of how the algorithm works from MathsANew