TAOCP 7.2.1.2 Exercise 1
Algorithm L spends its time determining, at each step, the two array positions $ a_{j-c_j+s} $ and $ a_{j-q+s} $ that must be interchanged, where $q = c_j + o_j$ and where the auxiliary variable $s$ c...
Section 7.2.1.2: Generating All Permutations
Exercise 1. ▶ [20] x 1. [20] Explain how to make Algorithm L run faster, by streamlining its operations when the value of j is near n.
Verified: no
Solve time: 1m48s
Solution
Algorithm L spends its time determining, at each step, the two array positions
$ a_{j-c_j+s} $ and $ a_{j-q+s} $ that must be interchanged, where $q = c_j + o_j$ and where the auxiliary variable $s$ counts how many indices $k > j$ satisfy $c_k = k - 1$. The costliest part of this computation is not the interchange itself, but the repeated formation of these indices, since each visit requires arithmetic with $j$, $c_j$, $s$, and a second evaluation after updating $q$.
When $j$ is near $n$, the structure of the state simplifies in a way that removes most of this overhead. The definition of $s$ implies that it only depends on indices strictly larger than $j$. If $j = n$, then no such indices exist, so $s = 0$ throughout that phase. If $j = n - 1$, then $s \in {0,1}$ and changes only when the condition $c_n = n - 1$ is met. For general $j = n - r$ with small $r$, the value of $s$ depends only on the last $r$ coordinates of the $c$ array, and its updates are localized.
A direct consequence is that, in the region where $j$ is close to $n$, the expressions $j - c_j + s$ and $j - q + s$ involve indices lying almost entirely in the suffix of the permutation. In that regime it is more efficient to represent the current permutation not only as the array $a_1, \dots, a_n$, but also with an inverse position array $p$ such that $p[a_i] = i$. This removes repeated scanning or recomputation of positional effects of updates, since every access to a location in $a$ can be translated immediately into a constant-time lookup in $p$ and vice versa.
With this representation, the interchange step no longer requires recomputing composite expressions to locate the affected entries. Instead, once $j$, $c_j$, $s$, and $q$ are known, the two positions to be swapped can be obtained by a constant number of arithmetic operations followed by two direct swaps in both $a$ and $p$. In the region $j \approx n$, this eliminates repeated recomputation of shifting offsets caused by $s$, since $s$ can be updated incrementally and stored as part of the state rather than recomputed from scratch in each execution of P3.
A further simplification occurs at the boundary $j = n$. In this case, every update of $c_n$ affects only the final coordinate, and the interchange indices reduce to $n - c_n$ and $n - q$, so no offset correction involving $s$ is needed at all. The transition step therefore becomes a pure update of the last few entries of $a$, $p$, and $c$, together with a sign flip of $o_n$ when required, without any dependence on earlier coordinates.
Thus, when $j$ is near $n$, Algorithm L can be accelerated by isolating the suffix dynamics: maintain the inverse permutation to avoid recomputing positions, update $s$ incrementally instead of recomputing it, and simplify the interchange formulas to direct indexed swaps that depend only on a bounded number of trailing components. This removes repeated recomputation of position expressions and reduces each step in the high-$j$ region to a constant number of array accesses and updates, independent of $n$.
This completes the solution. ∎