Tutorial :Fastest algorithm for circle shift N sized array for M position



Question:

What is the fastest algorithm for circle shifting array for m positions?
For example [3 4 5 2 3 1 4] shift m = 2 positions should be [1 4 3 4 5 2 3]

Thanks a lot


Solution:1

If you want O(n) time and no extra memory usage (since array was specified), use the algorithm from Jon Bentley's book, "Programming Pearls 2nd Edition". It swaps all the elements twice. Not as fast as using linked lists but uses less memory and is conceptually simple.

shiftArray( theArray, M ):      size = len( theArray )      assert( size > M )      reverseArray( theArray, 0, size - 1 )      reverseArray( theArray, 0, M - 1 )      reverseArray( theArray, M, size - 1 )  

reverseArray( anArray, startIndex, endIndex ) reverses the order of elements from startIndex to endIndex, inclusive.


Solution:2

It's just a matter of representation. Keep the current index as an integer variable and when traversing the array use modulo operator to know when to wrap around. Shifting is then only changing the value of the current index, wrapping it around the size of the array. This is of course O(1).

For example:

int index = 0;  Array a = new Array[SIZE];    get_next_element() {      index = (index + 1) % SIZE;       return a[index];  }    shift(int how_many) {      index = (index+how_many) % SIZE;  }  


Solution:3

Optimal solution

Question asked for fastest. Reversing three times is simplest but moves every element exactly twice, takes O(N) time and O(1) space. It is possible to circle shift an array moving each element exactly once also in O(N) time and O(1) space.

Idea

We can circle shift an array of length N=9 by M=1 with one cycle:

tmp = arr[0]; arr[0] = arr[1]; ... arr[7] = arr[8]; arr[8] = tmp;  

And if N=9, M=3 we can circle shift with three cycles:

  1. tmp = arr[0]; arr[0] = arr[3]; arr[3] = tmp;
  2. tmp = arr[1]; arr[1] = arr[4]; arr[4] = tmp;
  3. tmp = arr[2]; arr[2] = arr[5]; arr[5] = tmp;

Note each element is read once and written once.

Diagram of shifting N=9, M=3

Diagram of cycle shift

The first cycle is show in black with numbers indicating the order of operations. The second and third cycles are shown in grey.

The number of cycles required is the Greatest Common Divisor (GCD) of N and M. If the GCD is 3, we start a cycle at each of {0,1,2}. Calculating the GCD is fast with the binary GCD algorithm.

Example code:

// n is length(arr)  // shift is how many place to cycle shift left  void cycle_shift_left(int arr[], int n, int shift) {    int i, j, k, tmp;    if(n <= 1 || shift == 0) return;    shift = shift % n; // make sure shift isn't >n    int gcd = calc_GCD(n, shift);      for(i = 0; i < gcd; i++) {      // start cycle at i      tmp = arr[i];      for(j = i; 1; j = k) {        k = j+shift;        if(k >= n) k -= n; // wrap around if we go outside array        if(k == i) break; // end of cycle        arr[j] = arr[k];      }      arr[j] = tmp;    }  }  

Code in C for any array type:

// circle shift an array left (towards index zero)  // - ptr    array to shift  // - n      number of elements  // - es     size of elements in bytes  // - shift  number of places to shift left  void array_cycle_left(void *_ptr, size_t n, size_t es, size_t shift)  {    char *ptr = (char*)_ptr;    if(n <= 1 || !shift) return; // cannot mod by zero    shift = shift % n; // shift cannot be greater than n      // Using GCD    size_t i, j, k, gcd = calc_GCD(n, shift);    char tmp[es];      // i is initial starting position    // Copy from k -> j, stop if k == i, since arr[i] already overwritten    for(i = 0; i < gcd; i++) {      memcpy(tmp, ptr+es*i, es); // tmp = arr[i]      for(j = i; 1; j = k) {        k = j+shift;        if(k >= n) k -= n;        if(k == i) break;        memcpy(ptr+es*j, ptr+es*k, es); // arr[j] = arr[k];      }      memcpy(ptr+es*j, tmp, es); // arr[j] = tmp;    }  }    // cycle right shifts away from zero  void array_cycle_right(void *_ptr, size_t n, size_t es, size_t shift)  {    if(!n || !shift) return; // cannot mod by zero    shift = shift % n; // shift cannot be greater than n    // cycle right by `s` is equivalent to cycle left by `n - s`    array_cycle_left(_ptr, n, es, n - shift);  }    // Get Greatest Common Divisor using binary GCD algorithm  // http://en.wikipedia.org/wiki/Binary_GCD_algorithm  unsigned int calc_GCD(unsigned int a, unsigned int b)  {    unsigned int shift, tmp;      if(a == 0) return b;    if(b == 0) return a;      // Find power of two divisor    for(shift = 0; ((a | b) & 1) == 0; shift++) { a >>= 1; b >>= 1; }      // Remove remaining factors of two from a - they are not common    while((a & 1) == 0) a >>= 1;      do    {      // Remove remaining factors of two from b - they are not common      while((b & 1) == 0) b >>= 1;        if(a > b) { tmp = a; a = b; b = tmp; } // swap a,b      b = b - a;    }    while(b != 0);      return a << shift;  }  

Edit: This algorithm may also have better performance vs array reversal (when N is large and M is small) due to cache locality, since we are looping over the array in small steps.

Final note: if your array is small, triple reverse is simple. If you have a large array, it is worth the overhead of working out the GCD to reduce the number of moves by a factor of 2. Ref: http://www.geeksforgeeks.org/array-rotation/


Solution:4

Set it up with pointers, and it takes almost no time. Each element points to the next, and the "last" (there is no last; after all, you said it was circular) points to the first. One pointer to the "start" (first element), and maybe a length, and you have your array. Now, to do your shift, you just walk your start pointer along the circle.

Ask for a good algorithm, and you get sensible ideas. Ask for fastest, and you get weird ideas!


Solution:5

This algorithm runs in O(n) time and O(1) space. The idea is to trace each cyclic group in the shift (numbered by nextGroup variable).

var shiftLeft = function(list, m) {      var from = 0;      var val = list[from];      var nextGroup = 1;      for(var i = 0; i < list.length; i++) {          var to = ((from - m) + list.length) % list.length;          if(to == from)              break;            var temp = list[to];          list[to] = val;          from = to;          val = temp;            if(from < nextGroup) {              from = nextGroup++;              val = list[from];          }      }      return list;  }  


Solution:6

Depending on the data structure you use, you can do it in O(1). I think the fastest way is to hold the array in the form of a linked list, and have a hash table that can translate between "index" in the array to "pointer" to the entry. This way you can find the relevant heads and tails in O(1), and do the reconnection in O(1) (and update the hash table after the switch in O(1)). This of course would be a very "messy" solution, but if all you're interested in is the speed of the shift, that will do (on the expense of longer insertion and lookup in the array, but it will still remain O(1))

If you have the data in a pure array, I don't think you can avoid O(n).

Coding-wise, it depends on what language you are using.

In Python for example, you could "slice" it (assume n is the shift size):

result = original[-n:]+original[:-n]  

(I know that hash lookup is in theory not O(1) but we're practical here and not theoretical, at least I hope so...)


Solution:7

C arrayShiftRight function. If shift is negative the function shifts array left. It is optimized for less memory usage. Running time is O(n).

void arrayShiftRight(int array[], int size, int shift) {      int len;        //cut extra shift      shift %= size;        //if shift is less then 0 - redirect shifting left      if ( shift < 0 ) {          shift += size;      }        len = size - shift;        //choosing the algorithm which needs less memory      if ( shift < len ) {          //creating temporary array          int tmpArray[shift];            //filling tmp array          for ( int i = 0, j = len; i < shift; i++, j++ ) {              tmpArray[i] = array[j];          }            //shifting array          for ( int i = size - 1, j = i - shift; j >= 0; i--, j-- ) {              array[i] = array[j];          }            //inserting lost values from tmp array          for ( int i = 0; i < shift; i++ ) {              array[i] = tmpArray[i];          }      } else {          //creating temporary array          int tmpArray[len];            //filling tmp array          for ( int i = 0; i < len; i++ ) {              tmpArray[i] = array[i];          }            //shifting array          for ( int i = 0, j = len; j < size; i++, j++ ) {              array[i] = array[j];          }            //inserting lost values from tmp array          for ( int i = shift, j = 0; i < size; i++, j++ ) {              array[i] = tmpArray[j];          }      }  }  


Solution:8

def shift(nelements, k):             result = []      length = len(nelements)      start = (length - k) % length      for i in range(length):          result.append(nelements[(start + i) % length])      return result  

This code works well even on negative shift k


Solution:9

This should work to shift an arry circularly: Input : { 1, 2, 3, 5, 6, 7, 8 }; Output value present in array after the forloops : {8,7,1,2,3,5,6,8,7}

 class Program      {          static void Main(string[] args)          {              int[] array = { 1, 2, 3, 5, 6, 7, 8 };              int index = 2;              int[] tempArray = new int[array.Length];              array.CopyTo(tempArray, 0);                for (int i = 0; i < array.Length - index; i++)              {                  array[index + i] = tempArray[i];              }                for (int i = 0; i < index; i++)              {                  array[i] = tempArray[array.Length -1 - i];              }                      }      }  


Solution:10

Keep two indexes to the array, one index starts from beginning of the array to the end of array. Another index starts from the Mth position from last and loops through the last M elements any number of times. Takes O(n) at all times. No extra space required.

circleArray(Elements,M){   int size=size-of(Elements);     //first index   int i1=0;     assert(size>M)     //second index starting from mth position from the last   int i2=size-M;     //until first index reaches the end   while(i1<size-1){      //swap the elements of the array pointed by both indexes    swap(i1,i2,Elements);      //increment first pointer by 1    i1++;      //increment second pointer. if it goes out of array, come back to    //mth position from the last    if(++i2==size) i2=size-M;     }  }  


Solution:11

See this if you are interested in a Java implementation:

Programming Pearls: Circular Left/Right Shift Operation


Solution:12

static int [] shift(int arr[], int index, int k, int rem)  {      if(k <= 0 || arr == null || arr.length == 0 || rem == 0 || index >= arr.length)      {          return arr;      }        int temp = arr[index];        arr = shift(arr, (index+k) % arr.length, k, rem - 1);        arr[(index+k) % arr.length] = temp;        return arr;  }  


Solution:13

Ruby example:

def move_cyclic2 array, move_cnt    move_cnt = array.length - move_cnt % array.length     if !(move_cnt == 0 || move_cnt == array.length)                  array.replace( array[move_cnt..-1] + array[0...move_cnt] )      end     end  


Solution:14

In theory, the fastest one is a loop like this:

if (begin != middle && middle != end)  {      for (i = middle; ; )      {          swap(arr[begin++], arr[i++]);          if (begin == middle && i == end) { break; }          if (begin == middle) { middle = i; }          else if (i == end) { i = middle; }      }  }  

In practice, you should profile it and see.


Solution:15

Here is a nother one (C++):

void shift_vec(vector<int>& v, size_t a)  {      size_t max_s = v.size() / a;      for( size_t s = 1; s < max_s; ++s )          for( size_t i = 0; i < a; ++i )              swap( v[i], v[s*a+i] );      for( size_t i = 0; i < a; ++i )          swap( v[i], v[(max_s*a+i) % v.size()] );  }  

Of course it is not nearly as elegant as the famous reverse-three-times solution, but depending on the machine it can be similary fast.


Solution:16

circleArray has some errors and is not working in all cases!

The loop must continue while i1 < i2 NOT i1 < last - 1.

void Shift(int* _array, int _size, int _moves)  {      _moves = _size - _moves;      int i2 = _moves;           int i1 = -1;           while(++i1 < i2)      {          int tmp = _array[i2];          _array[i2] = _array[i1];          _array[i1] = tmp;          if(++i2 == _size) i2 = _moves;      }  }  


Solution:17

A friend of mine while joking asked me how to shift an array, I came up with this solutions (see ideone link), now I've seen yours, someone seems a bit esoteric.

Take a look here.

#include <iostream>    #include <assert.h>    #include <cstring>    using namespace std;    struct VeryElaboratedDataType  {      int a;      int b;  };    namespace amsoft  {      namespace inutils      {          enum EShiftDirection          {              Left,              Right          };  template   <typename T,size_t len>  void infernalShift(T infernalArray[],int positions,EShiftDirection direction = EShiftDirection::Right)  {      //assert the dudes      assert(len > 0 && "what dude?");      assert(positions >= 0 && "what dude?");        if(positions > 0)      {      ++positions;      //let's make it fit the range      positions %= len;        //if y want to live as a forcio, i'l get y change direction by force      if(!direction)      {          positions = len - positions;      }        // here I prepare a fine block of raw memory... allocate once per thread      static unsigned char WORK_BUFFER[len * sizeof(T)];      // std::memset (WORK_BUFFER,0,len * sizeof(T));      // clean or not clean?, well      // Hamlet is a prince, a prince does not clean        //copy the first chunk of data to the 0 position      std::memcpy(WORK_BUFFER,reinterpret_cast<unsigned char *>(infernalArray) + (positions)*sizeof(T),(len - positions)*sizeof(T));      //copy the second chunk of data to the len - positions position      std::memcpy(WORK_BUFFER+(len - positions)*sizeof(T),reinterpret_cast<unsigned char *>(infernalArray),positions * sizeof(T));        //now bulk copy back to original one      std::memcpy(reinterpret_cast<unsigned char *>(infernalArray),WORK_BUFFER,len * sizeof(T));        }    }  template   <typename T>  void printArray(T infernalArrayPrintable[],int len)  {          for(int i=0;i<len;i++)      {          std::cout << infernalArrayPrintable[i] << " ";      }      std::cout << std::endl;    }  template   <>  void printArray(VeryElaboratedDataType infernalArrayPrintable[],int len)  {          for(int i=0;i<len;i++)      {          std::cout << infernalArrayPrintable[i].a << "," << infernalArrayPrintable[i].b << " ";      }      std::cout << std::endl;    }  }  }          int main() {      // your code goes here      int myInfernalArray[] = {1,2,3,4,5,6,7,8,9};        VeryElaboratedDataType myInfernalArrayV[] = {{1,1},{2,2},{3,3},{4,4},{5,5},{6,6},{7,7},{8,8},{9,9}};      amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));      amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4);      amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));      amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,4,amsoft::inutils::EShiftDirection::Left);      amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));      amsoft::inutils::infernalShift<int,sizeof(myInfernalArray)/sizeof(int)>(myInfernalArray,10);      amsoft::inutils::printArray(myInfernalArray,sizeof(myInfernalArray)/sizeof(int));          amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));      amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4);      amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));      amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,4,amsoft::inutils::EShiftDirection::Left);      amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));      amsoft::inutils::infernalShift<VeryElaboratedDataType,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType)>(myInfernalArrayV,10);      amsoft::inutils::printArray(myInfernalArrayV,sizeof(myInfernalArrayV)/sizeof(VeryElaboratedDataType));        return 0;  }  


Solution:18

This method will do this work :

public static int[] solution1(int[] A, int K) {      int temp[] = new int[A.length];        int count = 0;        int orignalItration = (K < A.length) ? K :(K%A.length);           for (int i = orignalItration; i < A.length; i++) {          temp[i] = A[count++];      }      for (int i = 0; i < orignalItration; i++) {          temp[i] = A[count++];      }        return temp;  }  


Solution:19

Here is a simple and efficient general in place rotate function in C++, less than 10 lines.

which is excerpted from my answer on another question. How to rotate an array?

#include <iostream>  #include <vector>    // same logic with STL implementation, but simpler, since no return value needed.  template <typename Iterator>  void rotate_by_gcd_like_swap(Iterator first, Iterator mid, Iterator last) {      if (first == mid) return;      Iterator old = mid;      for (; mid != last;) {          std::iter_swap(first, mid);          ++first, ++mid;          if (first == old) old = mid; // left half exhausted          else if (mid == last) mid = old;      }  }    int main() {      using std::cout;      std::vector<int> v {0,1,2,3,4,5,6,7,8,9};      cout << "before rotate: ";      for (auto x: v) cout << x << ' '; cout << '\n';      int k = 7;      rotate_by_gcd_like_swap(v.begin(), v.begin() + k, v.end());      cout << " after rotate: ";      for (auto x: v) cout << x << ' '; cout << '\n';      cout << "sz = " << v.size() << ", k = " << k << '\n';  }  

Note:If u also have question or solution just comment us below or mail us on toontricks1994@gmail.com
Previous
Next Post »