TAOCP 7.2.1.2 Exercise 57
Step E5 performs the single operation a_{j-c_j+s} \leftrightarrow a_{j-q+s}.
Section 7.2.1.2: Generating All Permutations
Exercise 57. [HM22] [HM22] What is the average number of interchanges made in step E5?
Verified: no
Solve time: 1m46s
Solution
Step E5 performs the single operation
$$ a_{j-c_j+s} \leftrightarrow a_{j-q+s}. $$
This is one adjacent interchange of two elements of the permutation array $a_1,\dots,a_n$.
No other exchanges occur inside step E5. The remaining operations in E5 update $c_j$ and return control to $P2$, so they do not contribute to interchanges.
Thus, whenever step E5 is executed, the number of interchanges performed in that step is exactly $1$.
To compute the average number of interchanges made in step E5, it suffices to average this constant value over all executions of E5. Since every execution contributes exactly one interchange, the arithmetic mean over any set of executions is
$$ \frac{1 + 1 + \cdots + 1}{\text{number of executions}} = 1. $$
Therefore the average number of interchanges made in step E5 is
$$ \boxed{1}. $$
This completes the solution. ∎