scvalex.net

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.