Rotating a String solution

Identify the character you want to be at the front of the string after the rotation. Then divide the string into two halves such that this character is the first character in the second half. Reverse each half in place, then reverse the resulting string.

There is another O(n) solution. It has a better constant, but may or may not perform better in practice due to cache locality issues.

I call it the "two handed" algorithm, because you need "two hands" to do it. :-)

Basically, you pick up the characters in position 0 and position m, then you put down the character from position 0 into position m. Now holding only the character originally in position m, you pick up the character from position 2m and put down the new character for that position. When you reach a multiple of m that is past the end of the string, you wrap around to the beginning. Repeat until you are back at position 0.

If m and n were co-prime, you're already done. If not, then you need to repeat with positions 1, m+1, 2m+1, .., and then 2, m+2, 2m+2, .., and so on. You can stop at GCD(n,m), since this position will have been reached by the first loop starting at position 0.

Pseudocode:

num_cycles = GCD(n, m)
cycle_length = n / num_cycles

for cycle = 0 to num_cycles - 1
  index = cycle
  value = string[index]

  do
    index = (index + m) mod n
    -- Note: The following can be implemented as a swap.
    next_value = string[index]
    string[index] = value
    value = next_value
  loop while index <> cycle
end for

There's a simpler, more intuitive solution, which also more efficient. The trick is :

• Take the first letter.
• Compute where it should go after the rotate (addition with a modulo)
• Save the target letter in a temp variable X
• Replace the target letter by the first letter
• Compute where should X go after the rotate
• etc... n times, n being the length of the string.

Here a python snippet (sorry about the closing brackets, i don't know how to escape them):

def rotate_string(string, d):
     old_char = string[0)
     current_index = 0
     for i in range(len(string)):
          target_index = (current_index + d) % len(string)
          temp_char = string [ target_index )
          string [ target_index ) = old_char
          current_index = target_index
          old_char = temp_char
    return string

Here is a simpler solution that is also one-pass with n swaps. Start with 0 and place the element there where it should be (i -> i+m) with a swap. Repeat until you'd wrap around. You've now moved all of the string into place but the last m pieces. These are almost in place, but have been shifted n % m (remainder) places. So if necessary, shift them back recursively using the same algorithm.

I guess if m << n this version should have fairly nice cache-properties, be easy to unroll and work well enough with tail recursion optimization.

In Python:

def swap(a,i,j):
   a[i], a[j] = a[j], a[i]
def rotate(a,m,start=0):
   n=len(a)-start
   m = m % n
   if m != 0:
      for i in range(start,start+n-m):
         swap(a, i, i+m)
      rotate (a,m-n%m,start+n-m)

a = range(10)
rotate(a,3)
print a

This rotation problem has been part of algorithmic folklore since the 60s/70s. The solution provided by jliszka showed up as early as 1971 in a text editor written by Ken Thompson.

It is interesting because it is similar to the problem of swapping adjacent regions of memory.

jliskza's solution is probably the "best" solution. It is very simple and easy to implement. It is also both space and time efficient in practice.

logiclrd's solution is probably the worst. Algorithmically it has the best constant, but in practice it suffers poorly due to cache locality. Running some benchmarks on a 1.83GHz Intel dual core, it takes twice as long to run compared to the simple reversal algorithm.

Another algorithm that tends to be even faster than the reversal one is to use a recursive swap like this:

Given s, we want to rotate by m. This is equivalent to the problem s = ab, where we want to swap a and b, and a has length m. Change ab to ablbr, where br has the same length as a. Swap a and br to get brbla. Now we have the subproblem to solve, swapping brbl. This is the same format as the original problem and leads to a recursive solution.

This algorithm can be converted to an iterative version, and is described in Gries's Science of Programming (1981). Benchmarking on a 1.83GHz Intel dual core shows it is about twice as fast as the reversal algorithm.

All of these algorithms are also discussed in John Bentley's Programming Pearls.