Changes between Initial Version and Version 1 of Updates/Rotate Vector

Timestamp:

Jun 6, 2008, 12:13:58 AM (16 years ago)

Author:

Cory McWilliams

Comment:

--

Updates/Rotate Vector

@@ +1 @@
+= Remembering How to Rotate a Vector =
+For no reason that I can remember, I was recently reminded of a solution to a homework problem way back from my first semester in college that I thought was creative.  Having not had anything to say here for four months, I thought it would be fun to dig up the code and take a look.
+
+The challenge was to rotate a vector in place using constant extra memory and less than O(n^2^) moves.  There was very little additional information.  I remember scratching my head for a while and then coming up with this crazy scheme involving the greatest common divisor which I drew out in great detail with boxes and arrows explaining how everything would move.  I was disgusted that I couldn't arrive at a way to remove the gcd function entirely.
+
+Now that I look, I see it is an early problem in book ''Programming Pearls.''  Their solutions can be found [http://cm.bell-labs.com/cm/cs/pearls/rotate.c here].  Algorithm 3 is the closest to mine, and they indeed don't need to calculate the gcd ahead of time.
+
+Oh, and I was sloppy with whitespace and some other details back then.
+
+{{{
+#!cpp
+/* Euclid's algorithm for calculating the greatest common divisor of two numbers.
+        Taken from page 58 of "Data Structures & Algorithm Analysis in C++ Second Edition" by Mark Allen Weiss. */
+int gcd(int a, int b)
+{
+        while (b)
+        {
+                int r = a % b;
+                a = b;
+                b = r;
+        }
+
+        return a;
+}
+
+/* Rotates a vector i steps, using minimal moves.
+        This requires an "extra" calculation of the greatest common divisor of i and v.size(), but this algorithm
+        still wins out over rotating v one element at a time i times, because this is O(n) while the latter method is O(n^2) */
+template<class T> void rotate(vector<T> &v, int i)
+{
+        int size = v.size();
+        int factor = gcd(size, i);
+        i %= size;
+
+        int p;
+
+        for (p = 0; p < factor; p++)
+        {
+                int n;
+                T temp = v[p];  // Pull out one element so we can shift everything forward.
+                for (n = (p + i) % size; n != p; n = (n + i) % size)    // Until we get back to where we start, shift each element forward.
+                        v[(n - i + size) % size] = v[n];
+                        
+                v[(p - i + size) % size] = temp;        // Put back original element.
+        }
+}
+}}}
+
+[[AddComment]]