Section 5.2.2: Sorting by Exchanging

Exercise 2. [**] [M25]

(a) What is the minimum number of exchanges that will sort the permutation 376981452?

(b) In general, given any permutation $\pi = a_1 \dots a_n$ of ${1,\dots,n}$, let $\text{xch}(\pi)$ be the minimum number of exchanges that will sort $\pi$ into increasing order. Express $\text{xch}(\pi)$ in terms of “simpler” characteristics of $\pi$. (See exercise 5.1.4-41 for another way to measure the disorder of a permutation.)

Verified: yes
Solve time: 1m52s

(a) The permutation $376981452$ has the disjoint cycle decomposition

$$ (1,3,6,4,9,2,7)(5,8). $$

The first cycle has length $7$ and the second has length $2$. A cycle of length $m$ can be put into order with $m-1$ exchanges, and no fewer, since each exchange can increase the number of cycles by at most $1$. Hence the minimum number of exchanges required is

$$ (7-1)+(2-1)=7. $$

For example,

$$ 1\leftrightarrow3,\quad 1\leftrightarrow6,\quad 1\leftrightarrow4,\quad 1\leftrightarrow9,\quad 1\leftrightarrow2,\quad 1\leftrightarrow7,\quad 5\leftrightarrow8, $$

which performs exactly $7$ exchanges and sorts the permutation.

Thus the answer to (a) is

$$ \boxed{7}. $$

(b) Let $\pi$ be a permutation of ${1,\ldots,n}$, and let $c(\pi)$ denote the number of cycles in its disjoint cycle decomposition, counting fixed points as $1$-cycles. If the cycle lengths are $m_1,\ldots,m_r$, then

$$ m_1+\cdots+m_r=n, \qquad r=c(\pi). $$

Each cycle of length $m_i$ requires at least $m_i-1$ exchanges to become fixed, because every exchange can increase the number of cycles by at most $1$, and a cycle of length $m_i$ must be transformed into $m_i$ fixed-point cycles. Conversely, a cycle of length $m_i$ can be sorted in exactly $m_i-1$ exchanges by repeatedly exchanging one chosen element of the cycle with the element that belongs in its position.

Therefore the minimum number of exchanges needed to sort $\pi$ is

$$ \sum_{i=1}^r (m_i-1)

\left(\sum_{i=1}^r m_i\right)-r

n-c(\pi). $$

Hence

$$ \boxed{\operatorname{xch}(\pi)=n-c(\pi)}. $$

This completes the proof.

∎