 ## 33. Cycling Arrays

Here’s a challenge: cycle an array in-place. That is, given an array $$[x_0, x_1, \dots, x_{n-1}]$$ and a number $$m$$, you must make $$[x_m, x_{m+1}, \dots, x_{n-1}, x_0, x_1, \dots, x_{m-1}]$$ using only a constant amount of additional memory.

Solution: Here’s the solution presented by Jon Bently in Programming Pearls. The idea is to use three sub-array reversals.

First, reverse $$[0, m-1]$$ to get:

$[x_{m-1}, x_{m-2}, \dots, x_0, x_m, x_{m+1}, \dots, x_{n-1}]$

Second, reverse $$[m, n-1]$$ to get:

$[x_{m-1}, x_{m-2}, \dots, x_0, x_{n-1}, x_{n-2}, \dots, x_m]$

Finally, reverse $$[0, n-1]$$ to get:

$[x_m, x_{m+1}, \dots, x_{n-1}, x_0, x_1, \dots, x_{m-1}]$

In addition to its startling simplicity, this solution also has a lovely mnemonic: hold your hands in front so that you’re looking directly at your palms; flip one hand so that you can see it’s back; flip the other so that you’re now looking at the backs of your hands; now flip both hands together so that you see the palms again.

===----0    |    ----3    |    ----3    |    4----===
-\--1    |    ----2    |    ----2    |    5--/-
-|--2    |    ----1    |    ----1    |    6--|-
----3    | ===----0    | ===----0    |    7----
4----=== |    4----=== |    7----    | ===----0
5--/-    |    5--/-    |    6----    |    -\--1
6--|-    |    6--|-    |    5----    |    -|--2
7----    |    7----    |    4----=== |    ----3

Speaking of Programming Pearls, I think it’s one of the few coding books worth owning. It’s filled with clever solutions to all sorts of software problems and you uncover something new with every reading.