Problem: ¶

Given an Array of n elements, design an algorithm for rotating an Array right by i positions. Only O(1) additional storage is allowed.

Solution: ¶

The natural solution is to start from position the value at index k to k + i, repeatedly n times. This will work well if GCD(n,i) is != 1. However a general solution is to perform m jumps of size i, l times, but each time starting from the next index.

The first helper function is to perform m jumps of “size” each starting from a given index, wrapping around if necessary. For example if A = [1,2,3,4,5,6,7,8,9,10],

1m_rotations A 0 3 3

would cause the following jumps: 1 -> 4 -> 7, with A resulting in:

[1, 2, 3, 1, 5, 6, 4, 8, 9, 10]

1m_rotations xs index size m = elems (m_rotations' (arrayFromList xs 0) index (xs!!index) size m)
2    where
3        len = length xs
4        m_rotations' arr curr_index curr_value size numleft
5            | curr_index < 0 || size <= 0 || numleft <= 0 = arr
6            | otherwise = m_rotations' (arr // [(next_index, curr_value)]) next_index next_value size (numleft - 1)
7            where
8                next_index = mod (curr_index + size) len
9                next_value = arr!next_index

Now we create the actual rotator method that calls m_rotations k times, where k = gcd(|A|, j). This is:

 1rotate_array xs j = rotate_array' xs 0
 2    where
 3        lxs = length xs
 4        j' = mod j lxs
 5        gcd_lxs_j = greatest_common_divisor lxs j'
 6        numtimes = div lxs gcd_lxs_j
 7        rotate_array' xs start_index
 8            | start_index >= gcd_lxs_j = xs
 9            | otherwise = m_rotations ys (j' - (start_index + 1)) j' numtimes
10            where
11                ys = rotate_array' xs (start_index + 1)

A simpler algorithm to perform this is very similar to reversing words in a sentence:

1rotate_array_simple xs j = reverse (take j rxs) ++ reverse (drop j rxs)
2        where rxs = reverse x