Lesson 2

It is not difficult to see that, for any two permutations \(\pi_{1}\) and \(\pi_{2}\) of \(\{0,1,\dotsc,n-1\}\), the permutation \(\pi_{2}\) can be obtained from \(\pi_{1}\) by a sequence of at most \(n-1\) transpositions. This follows from the more general statement that, for any integer \(0 \le k \le n-1\), one can make at most \(k\) transpositions in \(\pi_{1}\) so that its first \(k\) elements become the same as those of \(\pi_{2}\). This suffices: if the first \(n-1\) elements of \(\pi_{1}\) and \(\pi_{2}\) coincide, then the remaining two elements coincide too.

This, in turn, can be proved by induction on \(k\). Indeed, the base case \(k=0\) is trivial. For the induction step from \(k-1\) to \(k\), we first perform \(k-1\) transpositions, as guaranteed by the induction hypothesis, so that the first \(k-1\) elements of \(\pi_{1}\) coincide with those of \(\pi_{2}\). If the \(k\)-th elements of \(\pi_{1}\) and \(\pi_{2}\) are already equal, that is, if \(\pi_{1}[k-1]=\pi_{2}[k-1]\), then there is nothing more to do. Otherwise, the element \(\pi_{2}[k-1]\) must occur somewhere to the right of position \(k-1\) in \(\pi_{1}\). Indeed, if there were an index \(i<k-1\) such that \(\pi_{1}[i]=\pi_{2}[k-1]\), then we would have \(\pi_{2}[i]=\pi_{1}[i]=\pi_{2}[k-1]\), which is impossible. Therefore, one additional exchange is enough to ensure that \(\pi_{1}[k-1]=\pi_{2}[k-1]\).

For example, to turn a permutation \((3, 0, 2, 1)\) into a permutation \((0, 1, 2, 3)\), one applies the following two transpositions: \((0, 1)\) and \((1, 3)\).