This post describes how to transform difficult problems involving permutations into easier problems involving graphs, then lists some problems that require this transformation and gives their solutions. In the process it demonstrates general techniques that may be useful in the face of such problems.
Introduction to permutations
A permutation of a set is a particular ordering of all the elements of the set. If we take the letters a, b, c, d, e, then c, d, b, e, a is a valid permutation, as is a, b, c, d, e or e, d, c, a, b or any other arrangement of these letters. a, c, e is not a permutation as it doesn't use all the elements, and a, a, b, c, d, e is also not a permutation because it uses an element more than once.
A permutation is a bijection from a set to itself, and permuting a sequence corresponds to applying the bijection element-wise to the sequence. If the set is $S = \{a, b, c, d, e\}$ and the permutation $f ~\colon~ S \to S$ is defined by $f(a) = b, f(b) = a, f(c) = e, f(d) = c, f(e) = d$, then applying this permutation to $a, b, c, d, e$ gives the sequence $f(a), f(b), \dots, f(e) = b, a, e, c, d$. The image of $f$ is also its domain so if $x \in S$, then $f(f(x)) \in S$, $f(f(f(x))) \in S$, and so on. In our permutation, $f(a) = b$ and $f(b) = a$, so $f(f(a)) = a$ and $f(f(b)) = b$. We say that $a$ is in a cycle of length 2 because it takes two applications of the permutation to $a$ to get back to $a$. $b$ is also in a cycle of length 2, and in fact we say that $a$ and $b$ are in the same cycle because to get back to $a$ by repeated applications of the permutation, we encounter $b$ and vice versa. In the same vein $c$ is in a cycle of length 3 along with $d$ and $e$. Every element of the set appears in exactly one cycle (note that it is possible to have a cycle of length 1) and cycles don't interact with each other. We say that any permutation can be written as a product of disjoint cycles.
Permutations can be represented as the union of a set of cycle graphs
Let's leave the world of algebra aside for a second and talk about graph theory. A directed graph is a set of vertices $V$ and edges $E$ where each edge maps from one vertex to another . A functional graph is a directed graph in which there is exactly one outgoing edge from each vertex. A permutation has a natural representation as a functional graph: let $V$ be the set on which the permutation is defined, and let there be an edge from $v_1$ to $v_2$ iff $f(v_1) = v_2$. The resulting graph is a specific class of functional graph where each vertex has exactly one incoming edge; in fact, the graph is the union of a set of cycle graphs, with each cycle graph corresponding to a disjoint cycle in the permutation.
Why do we care? This transformation allows us to transform problems about permutations into problems about graphs, and we know how to solve problems about graphs. In the rest of the post, I'll describe three different problems of increasing difficulty and show how to use this transformation to solve them. Without this transformation, these problems would be extremely difficult or impossible. The first problem describes a functional graph directly and the following two problems describe permutations.
Problem 1: a game involving a tennis ball
You are playing a game with $n-1$ other people and one tennis ball. You all sit in a circle and you hold the tennis ball in your hand. On the count of three, two things happen simultaneously:
You yell out a number $k$ between 2 and $n$ inclusive. Everyone in the circle points at exactly one other person in the circle. You can assume that all participants except for you choose someone in a uniformly random fashion. (By a simple symmetry argument, this means that it doesn't matter who you point to, so we can assume you also point uniformly randomly)You then throw the ball to the person you're pointing to, and they pass it to the person they're pointing to, and so on, so that the ball is passed a total of $k$ times. Whoever holds the ball at the end of $k$ passes loses the game.
What value of $k$ should you yell to minimise your chance of losing?
The underlying graph structure is immediately evident from the problem description: each player is a vertex and they point to each other to form a functional graph. The graph doesn't necessarily correspond to a permutation because it's possible for a vertex to have no incoming edges.
The solution follows from this line of reasoning: suppose you yell "2" and you lose. This means the ball was passed to whoever you pointed to ("Jane") and Jane returned it to you: you are in a cycle of size 2. Indeed, if you yell "2" you lose iff are in a cycle of size 2. Since each pointing arrangement (i.e. "valid graph" i.e. $n$-vertex functional graph with no cycles of length 1) is equally likely (proof left as exercise to the reader, but it's intuitive that if each person points uniformly randomly at someone else then all valid graphs are equally likely), we conclude that the probability of you losing is exactly the probability of randomly pulling a graph where you are in a cycle of size 2 from the uniform probability distribution over all valid graphs. This probability is equal to the number of valid graphs where you are in a cycle of size 2 divided by the total number of valid graphs.
Suppose you yelled "4" instead. If your graph happens to include you in a cycle of size 4, you will lose; but if you are in a cycle of size 2, you will also lose! And the number of valid graphs where you are in a cycle of size 2 OR a cycle of size 4 is obviously bigger than the number of valid graphs where you are only in a cycle of size 2. It follows that yelling "4" is always a worse choice than yelling 2. The same argument can be made for yelling 6, 8, and so on. In fact, the same argument can be made for yelling any composite number; it's always better to yell one of its prime factors instead.
In fact, this restricts us to yelling only primes. We just have to choose which prime. Some back-of-the-envelope combinatorial calculations show us the probability of being in a cycle of size 2 is $1/(n-1)$ which is larger than the probability of being in a cycle of size 3 which is larger than the probability of being in a cycle of length 5 and so on. The probability of being a member of a large cycle is smaller than the probability of being in a small cycle. We conclude that the solution to the problem is to choose $k$ to be the largest prime no greater than $n$.
The most interesting observation from this solution actually comes from the last few calculations that I skimmed: it turns out that large cycles in random functional graphs or large disjoint cycles in random permutations are extremely unlikely. In fact, the chance that you are in a cycle of length $n$ is $(n-1)!/(n-1)^{n-1}$. When $n=100$, this value in the order of $10^{-44}$.
Problem 2: 100 Prisoners Mk2
This is a variation on the classic 100 Prisoners problem.
The director of a prison offers 100 death row prisoners, who are numbered from 1 to 100, a last chance. A room contains a cupboard with 100 boxes in a row. The director randomly puts one prisoner's number in each closed box. The prisoners enter the room, one after another. Each prisoner may open and look into 50 boxes in any order. The boxes are closed again afterwards. If, during this search, every prisoner finds his number in one of the boxes, all prisoners are pardoned. If just one prisoner does not find his number, all prisoners die. Before the first prisoner enters the room, the prisoners may discuss strategy — but may not communicate once the first prisoner enters to look in the drawers.
The prisoners have also bribed a guard such that, before the prisoners commence the exercise, the guard goes into the room and is allowed to look into all the boxs and then swap the numbers in two boxes if the prisoners' strategy calls for it. The guard has no further communication with the prisoners after entering the room.
There is a strategy allowing all prisoners to survive. Find it.
The solution is to observe that the boxes can be numbered themselves from 1 to 100, in which case box $a$ containing the number of prisoner $b$ represents a permutation $f$ for which $f(a) = b$. Now suppose a prisoner $a$ enters the room and opens box $a$. $a$ points to $b$, which in turn points to $c$, and so on; since he is effectively re-applying the permutation (or walking the cycle graph, however you want to interpret it), he will eventually return to box $a$. But returning to box $a$ means opening a drawer containing prisoner number $a$ inside, which is the terminating condition.
The number of boxes the prisoner opens is exactly the size of the cycle in the graph containing his box. But what if this cycle is larger than size 50? Well, there can only be one such cycle in a graph of 100 vertices, and this is where the bribed guard plays his role! The guard first enters the room and determines if the graph corresponding to the arrangement of numbers contains a cycle of size 51 or more. If so, he simply breaks it into two smaller cycles by swapping two numbers in boxes. The resultant graph has no cycles larger than 50 vertices. Now all prisoners can follow this same strategy and all will survive. Brilliant!
The observation to take away from this problem is the same underlying graph/permutation can be interacted with in different ways (in this case it's walked along in different ways) but we take advantage of the fact that the graph/permutation itself is constant.
Problem 3: repeated number in array
Although the description for this problem is simple, it's an extremely difficult problem with a beautiful solution. It supposedly took Don Knuth 24 hours to solve; I discussed it with my team of Google engineers for over an hour and we concluded that it didn't have a solution. We were wrong.
Unlike the last problem, this problem benefits immensely from reducing it to a graph problem. However, now that you've seen the general strategy to solve problems of this type, I recommend you to attempt to solve it yourself before reading the solution.
Given an array of $n$ elements ranging from $1$ to $n-1$ in which exactly one element appears more than once, find the element in linear time and constant space without modifying the array.
Examples of arrays: [1, 2, 3, 4, 5, 5] or [4, 4, 4, 4, 1] or [6, 5, 2, 3, 5, 4, 1].
There's a trivial linear time and space solution using a flag array, and a fairly simple $O(n \log n)$ constant space solution using a modified binary search, but neither fulfils the requirements of the problem.
To solve it, notice that the first $n-1$ elements of the array are a permutation of the integers $1\dots n-1$, but where zero or the elements have been 'overwritten' with the integer $x$ in this range. If we try to construct the graph representing this almost-permutation, we get a functional graph where the vertex $V_x$ representing $x$ potentially has several incoming edges, and other vertices (the vertices representing overwritten array elements) now have no incoming edges. All components but one in the graph are cycle graphs, and the remaining component is rather messy: it comprises a cycle graph containing $V_x$ with a bunch of path graphs that enter the cycle at $V_x$. Note that the answer to the problem is $x$.
So far, we have ignored the final array element $k$ (represented by vertex $V_n$). $V_n$ has no incoming edges (since an incoming edge would mean there is an element $n$ somewhere in the array, which isn't possible because elements only range up to $n-1$) and one outgoing edge to vertex $V_k$ in the messy component of the functional graph described above. If we follow the edge from $V_n$ we go to $V_k$, and $V_k$ is either on a path graph to the messy component's cycle or it's on the cycle itself. So $V_n$ is the start of a path graph that ends at the messy component's cycle at vertex $V_x$.
Ignoring the vertices not in this path graph or the cycle it leads to, we end up with a rho-shaped graph, also sometimes (misleadingly) called a "linked list with a cycle", and if we find the length of the cycle, we can derive the length of the path graph preceding the cycle and hence find the vertex $V_x$ giving us the value $x$.
But we have efficient algorithms for finding cycles and their lengths! In particular, the hare and tortoise algorithm solves it in linear time and constant space.
In summary, the solution to the problem is to run a linear-time constant-space cycle detection algorithm on the implicit functional graph formed by the array beginning at its last element, and output the index in the array that corresponds to the vertex which starts the cycle.
The take-away here is that even problems that involve not-quite-permutations can be solved by relating the properties of the not-quite-permutation to the properties of permutations.
Conclusion
Problems that require interpreting an array as a permutation, or a permutation as a graph, are fairly rare. However, they often don't have alternative solutions, and if you haven't seen these tricks and techniques before, they can prove to be unsolvable.
