TAOCP 1.3.3 Exercise 8
Algorithm $B$ maintains a table $T$ such that, after a cycle has been completely scanned, the effect of that cycle has already been incorporated into the current permutation.
Section 1.3.3: Applications to Permutations
Exercise 8. [23] Would it be feasible to modify Algorithm $B$ to go from left to right instead of from right to left through the input?
Verified: yes
Solve time: 1m31s
Solution
Algorithm $B$ maintains a table $T$ such that, after a cycle has been completely scanned, the effect of that cycle has already been incorporated into the current permutation. The crucial step is
$$ \text{B3.}\qquad \text{exchange } Z \text{ and } T[i]. $$
When the input is scanned from right to left, the first symbol encountered in a cycle
$$ (x_1,x_2,\ldots,x_m) $$
is $x_m$, then $x_{m-1}$, ..., finally $x_1$. The variable $Z$ therefore carries the image that must be assigned next. After the sequence of exchanges in step B3, the entries are transformed as
$$ T[x_1]\leftarrow x_2,\qquad T[x_2]\leftarrow x_3,\qquad \ldots,\qquad T[x_m]\leftarrow x_1. $$
The matching left parenthesis is reached only after all elements of the cycle have been seen, so step B4 can complete the cycle by assigning the final value of $Z$ to the unique position $j$ that was left open. This is the reason that only a single temporary variable $Z$ is needed.
Suppose instead that the input were scanned from left to right. When the cycle
$$ (x_1,x_2,\ldots,x_m) $$
is read, the first element encountered is $x_1$. At that moment the algorithm must eventually make the assignment
$$ T[x_1]\leftarrow x_2, $$
but $x_2$ has not yet been seen. Similarly, after reading $x_2$ one must remember that
$$ T[x_2]\leftarrow x_3, $$
although $x_3$ is still unknown. Every element except the last therefore creates an unfinished assignment whose right-hand side will be determined only later.
For a cycle of length $m$, there are $m-1$ such unfinished assignments simultaneously present before the closing parenthesis is reached. Since $m$ is unbounded, a left-to-right version would require storage proportional to the length of the longest cycle currently being scanned. The single variable $Z$ is no longer sufficient.
Thus a left-to-right modification is possible only by introducing additional storage that records unresolved elements of the current cycle, essentially a stack or list of pending assignments. Such a procedure would lose the principal advantage of Algorithm $B$, namely that it processes the input in one pass while using only the table $T$ and a constant amount of auxiliary information.
Therefore a left-to-right version is not feasible if one wishes to preserve the essential structure and storage economy of Algorithm $B$; the right-to-left scan is what makes the single-pass method work. ∎