One way to solve a problem of size \(n\) is to pretend you can solve it for \(n-1\), and use that imaginary solution to solve it for \(n\). The approach is called recursion. Here’s an example showing how it works: enumerating all the ways to rearrange the elements of a list.
Given a list with \(n\) elements, \(\langle x_1, x_2, x_3, \ldots, x_n \rangle\), where the order of the elements matters, there are
\(n! = n \times (n-1) \times (n-2) \times \ldots \times 1\)
(“\(n\) factorial”) different ways to rearrange them (permutations). We can also write this out more formally as follows:
\(0! = 1\);
\(n! = n \times (n-1)!\), for \(n > 0\).
For example, consider the list \(\langle 1, 2,3 \rangle\), which I’ll just write 123 to save keystrokes. There are 3 elements and \(n! = 3 \times 2 \times 1 = 6\) permutations:
- 123
- 213
- 231
- 132
- 312
- 321
Using the more formal definition, the arithmetic goes:
\(3!\)
\(= 3 \times 2!\)
\(= 3 \times (2 \times 1!)\)
\(= 3 \times (2 \times (1 \times 0!))\)
\(= 3 \times (2 \times (1 \times 1))\)
\(= 6\)
To see how to enumerate all these, first start with the simplest list, \(\langle \ \rangle\). This is the empty list, the zero of the list world. There is exactly one way to arrange emptiness (\(0! = 1\)):
- \(\langle \ \rangle\)
That’s the problem solved for one list. There are infinitely many more, so we have a bit of work to do.
Now let’s return to the list 123, a list of length 3. Suppose (i.e., pretend) we knew all the permutations of 23 (a list of length 2). How could we use those to work out the permutations of 123.
It’s easy to see that there are two permutations of 23:
- 23
- 32
We go from those solutions to the solution for 123 by inserting 1 in all positions (beginning, middle, and end) of 23 and 32 in the following way:
- 123
- 213
- 231
- 132
- 312
- 321
I cheated a bit here, though. We haven’t developed a way to enumerate the permutations of 23. In a moment or two I want to write an R program to enumerate permutations of any list and R will need more explicit instructions.
Let’s go back a step and suppose we don’t know the permutations of 23 and want to enumerate them. Assume we know what the permutations are of a list with a single item, 3.
Now go back yet another step. How do we get the permutations of 3, assuming we know what they are for the next smallest list, the empty list, \(\langle \ \rangle\)?
We finally have an answer. As we saw above, there is one way to arrange emptiness: \(\langle \ \rangle\).
Following the same logic that allowed us to go from permutations of 23 to permutations of 123, we can go from from permutations of \(\langle \ \rangle\) to permutations of 3. We just have to insert 3 in all positions of the empty list. There is only one place to put it, giving a list with a single element, 3.
Now how do we go from the permutations of 3 to the permutations of 23? Simply place 2 in all positions of the one item list 3:
- 23
- 32
And so now our imagined solution actually exists.
We needed two steps:
- The base step, which solved the problem for the simplest list, the empty list \(\langle \ \rangle\).
- The inductive step, which uses permutations of the list of length \(n-1\), \(\langle x_2, x_3, \ldots, x_n \rangle\) and inserts \(x_1\) in all positions of those permutations to give us the permutations of a list of length \(n\), \(\langle x_1, x_2, x_3, \ldots, x_n \rangle\).
R
This translates straightforwardly to R as follows.
First, a function to insert an element \(x\) into all positions of a vector \(\mathit{xs}\):
insert_all <- function(x, xs) {
res <- list()
for (i in 0:length(xs))
res <- append(res, list(append(xs, x, i)))
res
}
For example:
> insert_all(1, 2:4) [[1]] [1] 1 2 3 4 [[2]] [1] 2 1 3 4 [[3]] [1] 2 3 1 4 [[4]] [1] 2 3 4 1
Now the actual permutation function, which takes a vector \(\mathit{xs}\) and returns a list of all its permutations:
perms <- function(xs) {
res <- list()
if (length(xs) == 0)
res <- list(c())
else {
ys <- perms(tail(xs, length(xs) - 1))
for (y in ys)
res <- append(res, insert_all(xs[1], y))
}
res
}
Note how perms is defined in terms of itself. The line
perms(tail(xs, length(xs) - 1))
removes the first element of the list and calls itself again. It keeps doing this until it is called with an empty vector, when it returns a list with an empty vector,
list(c())
Then insert_all pieces everything together.
Let’s give perms a go with the list 1234. There should be \(4! = 24\) permutations:
> perms(1:4) [[1]] [1] 1 2 3 4 [[2]] [1] 2 1 3 4 [[3]] [1] 2 3 1 4 [[4]] [1] 2 3 4 1 [[5]] [1] 1 3 2 4 [[6]] [1] 3 1 2 4 [[7]] [1] 3 2 1 4 [[8]] [1] 3 2 4 1 [[9]] [1] 1 3 4 2 [[10]] [1] 3 1 4 2 [[11]] [1] 3 4 1 2 [[12]] [1] 3 4 2 1 [[13]] [1] 1 2 4 3 [[14]] [1] 2 1 4 3 [[15]] [1] 2 4 1 3 [[16]] [1] 2 4 3 1 [[17]] [1] 1 4 2 3 [[18]] [1] 4 1 2 3 [[19]] [1] 4 2 1 3 [[20]] [1] 4 2 3 1 [[21]] [1] 1 4 3 2 [[22]] [1] 4 1 3 2 [[23]] [1] 4 3 1 2 [[24]] [1] 4 3 2 1
It works!
Factorial
Understanding how to enumerate permutations also shows us how to count them. In other words, it shows us how to define factorial.
Pretend we don’t know what factorial is. We’re making a new one called “factorial?” (pronounce with rising intonation), such that \(n?\) is the number of permutations of a list of length \(n\). We hope that by the end of process, \(n? = n!\).
Recall again that there’s only one way to arrange emptiness, so
\(0? = 1\).
Suppose we know how to count the number of permutations of a list of length \(n-1\), that is, we know what \((n-1)?\) is. How would we use the answer to that to tell us what \(n?\) is?
If we know \((n-1)?\), that means we know the number of permutations of lists of length \(n-1\).
The length of each list counted by \((n-1)?\) must be \(n-1\). We saw when enumerating permutations that we have to add an extra element to all positions of each element in those lists. That’s \(n\) positions to add the extra element to, and we need to do it \((n-1)?\) times, so we just multiply:
\(n? = n \times (n-1)?\), for \(n > 0\).
It turns out that indeed \(n? = n!\), as defined at the top of this post.