Tuesday 24 September 2013

Algorithms: Rotating a one-dimensional array of n elements by i positions

This post is now being maintained at my new blog.

I encountered this problem while reading [1] and I have to admit, it takes some effort to get to the bottom of it. Here is the precise problem specification.

"Rotate a one-dimensional vector of n elements left by i positions. For instance, with n = 8 and i = 3, the vector abcdefgh is rotated to defghabc."
Think about it. Take your time...

Solution 1: Using an additional buffer

The first solution which I could think, which was one of the two embarrassingly naive solutions I could think over the top of my head, is making use of an additional buffer. We copy the first i bits to the additional temporary buffer, move the next n - i bits to the beginning of our array and then copy back the i bits from the temporary buffer to our original array.

template<class T>
void rotate_array(std::vector<T> *array, int i) {
  int n = array->size();
  i = i % n;
  std::vector<T> *temp_array = new std::vector<T>(array->begin(), array->begin() + i);
  std::copy(array->begin() + i, array->end(), array->begin());
  std::copy(temp_array->begin(), temp_array->end(), array->begin() + n - i);
  delete temp_array;
}
You can see that solution one is fast, it takes O(n) time which is optimal. On the downside, it requires an additional buffer of size min(i, n - i) which is nothing but O(n). Clearly not a good solution.

Solution 2: Rotating the array by 1, i times

The second solution which I could think is by repeatedly rotating the array left by 1, i times. Rotating left by 1 is quite straight forward. Save the first element, swap each pair of consecutive elements and put the saved element at the end. Here is the code.

template<class T>
void rotate_array_by_one(std::vector<T> *array) {
  for (int i = 0; i < array->size() - 1; i++) {
    std::swap(array->at(i), array->at(i + 1));
  }
}

template<class T>
void rotate_array(std::vector<T> *array, int i) {
  int n = array->size();
  i = i % n;
  for (int j = 0; j < i; j++) {
    rotate_array_by_one<T>(array);
  }
}
This solution trades time for space and ends up having a space complexity of O(n) but a time complexity of O(n2). What next?

Solution 3: Rotating the array by i, using a special trick

Let's think why is it not possible to directly swap across i elements, similar to solution two, just across i elements instead of neighbors. We save the first elements, swap the first element with ith element, the ith element with the 2ith element and so on modulo n. We cycle through the array until we reach where we started. Did we cycle through all the elements? If yes, well and good. If not we have to repeat the process with 'untouched' elements. How do we keep a track?
The greatest common divisor of i and n is the number of cycles to be permuted. In terms of modern algebra, it is the number of cosets in the permutation group induced by the rotation. [1]

int gcd(int a, int b) {
  while (a != 0) {
    int c = a;
    a = b % a;
    b = c;
  }
  return b;
}

template<class T>
void rotate_array(std::vector<T> *array, int i) {
  int n = array->size();
  i = i % n;
  int gcd_n_i = gcd(i, n);
  for (int j = 0; j < gcd_n_i; j++) {
    for (int k = j; (k + i) % n != j; k = (k + i) % n) {
      std::swap(array->at(k), array->at((k + i) % n));
    }
  }
}
We have done it! We have a solution which is fast (O(n)) and takes up no extra space. But when I think about it this solution is by no means straight forward. Apart from the fact that a knowledge of number theory is required for this solution, it requires some subtle programming difficult to get right on the first attempt.

Solution 4: The winner, array reversal!

Have a look at the solution, it took less than a minute to type out and was correct in the first attempt, it speaks for itself.

template<class T>
void rotate_array(std::vector<T> *array, int i) {
  int n = array->size();
  i = i % n;
  std::reverse(array->begin(), array->begin() + i);
  std::reverse(array->begin() + i, array->end());
  std::reverse(array->begin(), array->end());
}
I just loved this solution.
Does it really need an explanation?

{1] Programming Pearls, Second Edition, by Jon Bentley.

4 comments: