TAOCP 7.2.1.2 Exercise 58
Algorithm E generates all permutations by a sequence of adjacent interchanges and returns to the starting permutation, as indicated by its structure involving steps $E2$ and $E5$, and by the cyclic in...
Section 7.2.1.2: Generating All Permutations
Exercise 58. [M21] [M21] True or false: If Algorithm E begins with a0 . . . an−1 = x1 . . . xn then the final permutation visited begins with a0 = xn.
Verified: no
Solve time: 2m51s
Solution
Algorithm E generates all permutations by a sequence of adjacent interchanges and returns to the starting permutation, as indicated by its structure involving steps $E2$ and $E5$, and by the cyclic interpretation used in Exercises 55–57 where the permutations are traversed via minimal-change transitions. Thus the execution forms a Hamiltonian cycle in the Cayley graph of $S_n$ generated by adjacent transpositions.
Let the initial permutation be
$a_0 a_1 \ldots a_{n-1} = x_1 x_2 \ldots x_n.$
Since every transition in Algorithm E, including step $E5$, consists of swapping two adjacent entries, every edge of the generated cycle corresponds to a single adjacent transposition. When the cycle returns to the initial permutation, the final transition must also be a single adjacent interchange applied to the initial ordering, since the last visited permutation must be connected to the first by one valid step of the same type.
Hence the final permutation $y_0 y_1 \ldots y_{n-1}$ differs from $x_1 x_2 \ldots x_n$ by exactly one adjacent swap at some position $k$, with $1 \le k \le n-1$, giving either
$y_0 \neq x_1 \text{ only when } k = 1,$
and otherwise $y_0 = x_1$.
No structural constraint in Algorithm E forces the final adjacent interchange to involve position $n-1$ and $n$. The location of the closing interchange depends on the internal state of the algorithm when the cycle completes, not on a fixed endpoint condition that would systematically move $x_n$ into the first position.
Therefore $y_0$ is either $x_1$ or $x_2$, depending on whether the final interchange occurs at the first or second position, and it is not determined to be $x_n$ for general $n$.
The claim that the final permutation begins with $a_0 = x_n$ is therefore false.
$\boxed{\text{false}}$