TAOCP 7.2.1.2 Exercise 97

Section 7.2.1.2: Generating All Permutations

Exercise 97. [21] [21] Discuss how to generate all derangements of {1, . . . , n}, namely those a1 . . . an such that a1 ̸= 1, a2 ̸= 2, a3 ̸= 3, . . . .

Verified: no
Solve time: 6m52s

Solution

Let $n > c_t > \cdots > c_1 \ge 0$ with the constraints from exercise 57 and the additional condition

$c_{j+1} > c_j + 1 \qquad (t > j \ge 1).$

Define the shifted variables

$d_j = c_j - (j-1), \qquad 1 \le j \le t.$

Then for $t > j \ge 1$,

$d_{j+1} = c_{j+1} - j \ge (c_j + 2) - j = (c_j - (j-1)) + 1 = d_j + 1,$

$n - t + 1 > d_t > \cdots > d_1 \ge 0.$

The upper bound follows from $c_t \le n-1$, hence

$d_t = c_t - (t-1) \le (n-1) - (t-1) = n - t.$

Thus the mapping $c \mapsto d$ is a bijection between admissible sequences $c_1 < \cdots < c_t$ with no adjacent indices and ordinary $t$-combinations drawn from ${0,1,\dots,n-t}$.

The span constraint transforms as well. From $c_t - c_1 < m$,

$c_t - c_1 = (d_t + t - 1) - d_1 = (d_t - d_1) + (t-1),$

$d_t - d_1 < m - (t-1).$

Hence admissible chords correspond exactly to sequences

$n' > d_t > \cdots > d_1 \ge 0,$

with

$n' = n - t + 1,$

together with the reduced span condition

$d_t - d_1 < m - (t-1).$

This reduces the problem to the piano player problem of exercise 57 applied to the parameters $n'$ and $m' = m - (t-1)$.

For generation, apply Algorithm $L$ from Section 7.2.1.3 to the variables $d_t \cdots d_1$ with the modified bound $n' = n - t + 1$, while retaining the same acceptance test for the span condition. The algorithm visits all combinations in lexicographic order, and each valid chord is obtained by transforming back via

$c_j = d_j + (j-1), \qquad 1 \le j \le t.$

Correctness follows from the bijection between admissible $c$-sequences and admissible $d$-sequences, since each transformation preserves and reflects both the ordering constraints and the span inequality. This completes the proof. ∎