From Mathematics to Generic Programming

11. Permutation Algorithms

An algorithm must be seen to be believed.

Donald Knuth

Complex computer programs are built up from smaller pieces that perform commonly used fundamental tasks. In the previous chapter, we looked at some tasks involving searching for data. In this chapter, we’ll look at tasks that involve shifting data into new positions, and show how to implement them in a generic way. We’ll see how these tasks also end up using two ideas discussed earlier in the book: groups from abstract algebra and the greatest common divisor (GCD) from number theory.

The tasks we will focus on—rotate and reverse—allow us to introduce algorithms that do the same task differently depending on the concept of the iterator to which they apply. In addition ...