TAOCP 1.3.3 Exercise 13

Section 1.3.3: Applications to Permutations

Exercise 13. [M24] Prove that Algorithm $J$ is valid.

Verified: yes
Solve time: 9m43s

Let the current permutation be

$$ P = (a_1,a_2,\dots,a_n). $$

Algorithm $J$ constructs a new permutation $Q$ as follows:

Choose the largest index $i$ such that $a_i < a_{i+1}$.
Choose the largest index $j>i$ such that $a_j > a_i$.
Swap $a_i$ and $a_j$.
Reverse the suffix $a_{i+1},\dots,a_n$.

We prove that this procedure is valid, meaning it produces the lexicographically next permutation when it does not terminate, and it enumerates all permutations exactly once.

1. Structure of the suffix before the swap

Let $i$ be chosen as in Step 1. Then for every $k \ge i+1$,

$$ a_k \ge a_{k+1}. $$

If not, suppose there exists $k \ge i+1$ such that $a_k < a_{k+1}$. Then $k > i$, contradicting the maximality of $i$. Hence the suffix

$$ S = (a_{i+1},\dots,a_n) $$

is weakly decreasing.

2. Existence and meaning of $j$

Since $a_i < a_{i+1}$, at least one element in the suffix is greater than $a_i$, so the set ${k>i : a_k > a_i}$ is nonempty. Let $j$ be its largest element.

Because $S$ is weakly decreasing, values in the suffix decrease as indices increase. Therefore, among all entries greater than $a_i$, the largest index $j$ corresponds to the smallest value greater than $a_i$ in the suffix.

3. Effect of the swap

After swapping $a_i$ and $a_j$, define the new sequence

$$ (a_1,\dots,a_{i-1},a_j, a_{i+1},\dots,a_{j-1},a_i,a_{j+1},\dots,a_n). $$

Call the suffix after the swap

$$ T = (a_{i+1},\dots,a_{j-1},a_i,a_{j+1},\dots,a_n). $$

We prove that $T$ is weakly decreasing.

The segment $a_{i+1},\dots,a_{j-1}$ was already weakly decreasing.
In the original suffix, we had

$$ a_{j-1} \ge a_j. $$

After the swap, $a_j$ is replaced by $a_i$, and since $a_j > a_i$, we have

$$ a_{j-1} \ge a_j > a_i, $$

hence

$$ a_{j-1} \ge a_i. $$

For positions after $j$, nothing changes.

Thus every adjacent pair in $T$ is in nonincreasing order, so $T$ is weakly decreasing.

4. Why reversal produces the minimal suffix

Since $T$ is weakly decreasing, reversing it produces a weakly increasing sequence. Therefore, after Step 4, the suffix becomes the elements of $T$ arranged in increasing order.

This is the lexicographically smallest arrangement of the multiset of suffix elements, because among all permutations of a multiset, increasing order is minimal in lexicographic order.

5. Why $Q$ is the immediate lexicographic successor of $P$

(a) $Q > P$

The first $i-1$ entries are unchanged. At position $i$,

$$ Q_i = a_j > a_i = P_i, $$

so $Q > P$.

(b) No permutation lies strictly between $P$ and $Q$

Let $R$ be any permutation with $P < R$. Let $k$ be the first index where $R$ and $P$ differ. Then $R_k > a_k$.

We show $k \ge i$.

If $k < i$, then $Q_k = P_k$, so comparing $R$ and $Q$, we have $R_k > Q_k$, hence $R > Q$, contradicting $R < Q$. So $k \ge i$.

Now consider $k = i$. Then $R_i > a_i$. Any value greater than $a_i$ occurring in the suffix must be at least $a_j$, because in a weakly decreasing suffix the largest index with $> a_i$ corresponds to the smallest such value. Hence:

$$ R_i \ge a_j. $$

If $R_i > a_j$, then $R > Q$.
If $R_i = a_j$, then both $R$ and $Q$ agree at position $i$, and the comparison moves to the suffix. But the suffix of $Q$ is in increasing order, hence lexicographically minimal among all arrangements of those elements. Any deviation from it makes the permutation larger than $Q$.

Thus no permutation lies strictly between $P$ and $Q$. Therefore $Q$ is the lexicographic successor of $P$.

6. Uniqueness of transitions

For each non-maximum permutation $P$, the indices $i$ and $j$ are uniquely determined:

$i$ is uniquely the rightmost ascent.
$j$ is uniquely the rightmost element greater than $a_i$.

Hence the transformation $P \mapsto Q$ is a well-defined function on permutations, so no permutation can have two different successors.

7. Termination and completeness

The algorithm terminates exactly when no index $i$ satisfies $a_i < a_{i+1}$, i.e. when the permutation is weakly decreasing. This is the lexicographically largest permutation.

Since each step produces the unique lexicographic successor and there are only $n!$ permutations, the process visits each permutation exactly once and must terminate after $n!$ steps.

Conclusion

Algorithm $J$ is valid because:

It always produces the lexicographically next permutation when not at the final one.
Each step is uniquely determined.
It terminates exactly at the final (descending) permutation.
Every permutation is generated exactly once.

Hence Algorithm $J$ correctly enumerates all permutations in lexicographic order. ∎