C++ implements one dimensional vector rotation algorithm

In the second chapter of the book "programming abas", five ideas of n dimensional vector rotation algorithm (also known as array cyclic shift algorithm) are mentioned, and their differences and advantages and disadvantages in time and space performance are compared. This paper will make an in-depth analysis of this algorithm. The details are as follows:

I. problem description

Rotate an n dimensional vector by I positions to the left. For example, suppose n=8, I =3, and the vector abcdefgh is rotated as the vector defghabc. Simple code does the job in n steps using an n - bit intermediate vector. Can you use only a few dozen extra bytes of memory to rotate the vector in time proportional to n?

Ii. Solutions

Thinking a : copies the first I elements of vector x into a temporary array, then moves the remaining n-i elements I positions to the left, and then copies the first I elements from the temporary array to the rest of x.

Performance: this method USES I extra locations, and if I is large, it consumes too much storage space.

C++ code as follows:

 
#include<iostream> 
#include<string> 
using namespace std; 
 
int main() 
{ 
  string s = "abcdefghijklmn"; 
  cout << "The origin is: " << s << endl; 
  //The number of the left
  int i; 
  cin >> i; 
  if(i > s.size()) 
  { 
    i = i%s.size(); 
  } 
  //Save the first I elements temporarily
  string tmp(s, 0, i); 
  //Move the rest to the left by I positions
  for(int  j=i; j<s.size(); ++j) 
  { 
    s[j-i] = s[j]; 
  } 
  s = s.substr(0, s.size()-i) + tmp; 
  cout << "The result is: "<< s << endl; 
  return 0; 
} 

Idea 2 : defines a function that rotates x to the left by a position (its time is proportional to n) and then calls the function I times.

Performance: this approach, despite the space complexity of O(1), produces excessive runtime consumption.

C++ code as follows:

 
#include<iostream> 
#include<string> 
using namespace std; 
 
void rotateOnce(string &s) 
{ 
  char tmp = s[0]; 
  int i; 
  for(i=1; i<s.size(); ++i) 
  { 
    s[i-1] = s[i]; 
  } 
  s[i-1] = tmp; 
} 
 
int main() 
{ 
  string s = "abcdefghijklmn"; 
  cout << "The origin is: " << s << endl; 
  //The number of the left
  int i; 
  cin >> i; 
  if(i > s.size()) 
  { 
    i = i%s.size(); 
  } 
  //Call the function I times
  while(i--) 
  { 
    rotateOnce(s); 
  } 
  cout << "The result is: "<< s << endl; 
  return 0; 
} 

Thought three : move x[0] to the temporary variable t, then move x[I] to x[0], x[2i] to x[I], and so on, until we return to the position of x[0] to extract the element, this time to extract the element from the temporary variable t, and then end the process (when the subscript is greater than n to take the modulus or minus n). If the process does not move all the elements, it moves again from x[1], moving the maximum convention of I and n several times in total.

Performance: this method is ingenious and, as the book suggests, a masterful acrobatic feat. The space complexity is O(1) and the time complexity is linear time, which satisfies the performance requirements of the problem, but is not optimal.

C++ code as follows:

 
#include<iostream> 
#include<string> 
using namespace std; 
 
//Euclid's algorithm finds the greatest common divisor
int gcd(int i, int j) 
{ 
  while(1) 
  { 
    if(i > j) 
    { 
      i = i%j; 
      if(i == 0) 
      { 
        return j; 
      } 
    } 
    if(j > i) 
    { 
      j = j%i; 
      if(j == 0) 
      { 
        return i; 
      } 
    } 
  } 
} 
 
int main() 
{ 
  string s = "abcdefghijklmn"; 
  cout << "The origin is: "<< s << endl; 
  //The number of the left
  int i; 
  cin >> i; 
  if(i > s.size()) 
  { 
    i = i%s.size(); 
  } 
  //mobile
  char tmp; 
  int times = gcd(s.size(), i); 
  for(int j=0; j<times; ++j) 
  { 
    tmp = s[j]; 
    int pre = j; //Record the last location
    while(1) 
    { 
      int t = pre+i; 
      if(t >= s.size()) 
        t = t-s.size(); 
      if(t == j) //All the way to the original position of TMP, j
        break; 
      s[pre] = s[t]; 
      pre = t; 
    } 
    s[pre] = tmp; 
  } 
  cout << "The result is: "<< s << endl; 
  return 0; 
} 

Thinking four : the rotation vector x is actually the exchange of two segments of the vector ab, resulting in the vector ba, where a represents the first I elements of x. Let's say a is shorter than b. B is divided into bl and br so that the length of br is the same as the length of a. Switch a and br, convert ablbr to brbla. Now that sequence a is in its final position, we can focus on swapping the two parts of b. Since the new problem is the same as the original one, we solve it recursively. This approach produces elegant programs, but requires clever code and some thought to see that it is efficient enough.

// implementation code (omitted)  

Thinking five (preferably) think of this problem as converting an array ab to a ba, and assume that we have a function to reverse the elements of a particular part of the array. You start with ab, you take the inverse of a, you get arb, and then you take the inverse of b, you get arbr. And then you take the inverse of the whole thing, and you get arbr, r, which is ba.

reverse(0, i-1)  
reverse(i, n-1) 
reverse(0, n-1) 

Performance: the reverse-order method is efficient in time and space, and the code is very short and hard to fault.

C++ code as follows:

 
#include<iostream> 
#include<string> 
using namespace std; 
 
void reverse(string &s, int begin, int end) 
{ 
  while(begin < end) 
  { 
    char tmp = s[begin]; 
    s[begin] = s[end]; 
    s[end] = tmp; 
    ++begin; 
    --end; 
  } 
} 
 
int main() 
{ 
  string s = "abcdefghijklmn"; 
  cout << "The origin is: "<< s << endl; 
   
  int i; 
  cin >> i; 
  if(i > s.size()) 
  { 
    i = i%s.size(); 
  } 
 
  reverse(s, 0, i-1); 
  reverse(s, i, s.size()-1); 
  reverse(s, 0, s.size()-1); 
 
  cout << "The result is: "<< s << endl; 
  return 0; 
} 

Third, expand and extend

How do I rotate vector ABC into cba?

Similar to the previous problem, this vector rotation corresponds to the swap model for non-contiguous memory blocks. The solution is similar: cba = (arbrcr) r

Note: in the interview or written test, if there is a vector rotation (memory block exchange) problem, it is recommended that the best way to use five answers, not only efficient and concise.