Rotate a one-dimensional array of N elements left by k positions

We can find the discussion of this problem in Bentley's book Programming Pears, Column 2.

First Solution

First observation is that we can decompose a rotation into several swap. This idea will lead us to find the recursive structure of the problem. Here is the implementation

let rec rotate arr is ie k i0 j0 =
  let kk = k mod (ie-is+1) in
  if is < ie && kk <> 0 then
    let condition_i0 = i0 < kk
    and condition_j0 = (is+j0) < ie in
    if condition_i0 then
      let tmp = arr.(is+i0) in
      arr.(is+i0) <- arr.(is+j0);
      arr.(is+j0) <- tmp;
      match condition_j0 with
      | true -> rotate arr is ie kk (i0+1) (j0+1)
      | false ->  let kk2 = kk - i0 - 1 in rotate arr (is+i0+1) ie kk2 0 kk2
    else
      rotate arr (is+kk) ie kk 0 kk
;;

Second Solution

We can also look at this problem from another point of view. We can decompose the rotation into several sub-rotation.

0  <- k <- 2k <- 3k ...
1 <- k+1 < 2k+1 <- 3k+1 <- ...

This idea leas to another solution.

let rec gcd a b =
  let x = min a b and y = max a b in
  if x = 0 then y
  else
    gcd x (y mod x ) ;;

let rotate2 arr k =
  let length = Array.length arr in
  let kk = k mod length in
  let n_loop = gcd kk length in
  let n_loop_j = length / n_loop in
  for i = 0 to n_loop - 1 do
    let tmp = arr.(i) in
    for j = 0 to n_loop_j - 2 do
      arr.((i+ j * kk) mod length) <- arr.((i + (j+1) * kk) mod length )
    done ;
    arr.((i + (n_loop_j-1) * kk) mod length) <- tmp
  done ;;

Third Solution

In the book we can find a third solution and it is very elegant.

rotate(n,k) = {reverse(n,0,k-1);
                       reverse(n,k,n-1);
                       reverse(n,0,n-1);}