TAOCP 7.2.1.2 Exercise 91

Section 7.2.1.2: Generating All Permutations

Exercise 91. [HM21] [HM21] Analyze the running time of Algorithm V when it is used with the relations (49) to find perfect matchings.

Verified: no
Solve time: 5m14s

Solution

Let the set of elements be ${1,2,\dots,2n}$ and let the relations (49) specify a perfect matching, so the elements are partitioned into $n$ disjoint pairs ${x_i,y_i}$, each pair inducing a constraint of comparability in exactly the form used by Algorithm V for inverse topological sorting.

A permutation is feasible precisely when it respects all pair relations, hence each valid output corresponds to a linear extension of a poset consisting of $n$ disjoint two-element chains. Every such poset admits no interaction between different chains, so feasibility depends only on internal ordering within each pair and on interleavings of the pairs.

Each pair contributes exactly two possible local orders, and the global structure reduces to choosing an interleaving of $n$ two-element blocks together with orientation choices within each block. This produces a one-to-one correspondence between feasible permutations and perfect matchings on $2n$ labeled items together with block interleavings consistent with those matchings.

The number of perfect matchings on $2n$ elements is

$$ M_n = \frac{(2n)!}{2^n n!}, $$

since the first element has $2n-1$ choices, the next unmatched element has $2n-3$ choices, continuing until $1$.

Algorithm V performs a systematic enumeration of all linear extensions by maintaining a state vector and repeatedly updating a coordinate $k$ determined by the relation structure. In the present case each element participates in exactly one relation, so the dependency graph has maximum degree $1$, and every update of $k$ is triggered by a single violated or saturated pair constraint.

For a fixed pair ${x_i,y_i}$, the inversion-state evolution induced by Algorithm V changes only when the algorithm attempts to invert that pair or restore its order. Each such event corresponds to a constant number of updates of the auxiliary variables governing the current coordinate, since no cascade through other constraints is possible.

Hence, between two successive visits to permutations differing only in interleaving, Algorithm V performs a bounded number of updates of the controlling variables $k$ and the associated counters from (51), with a bound independent of $n$. This follows because every change in direction or backtracking step is localized to a single pair constraint and does not propagate through a chain of length exceeding $1$.

Each generated permutation contains $2n$ symbols, so any algorithm that outputs all feasible permutations must spend at least $\Omega(2n)$ time per output simply to write the result. Therefore any total running time is bounded below by

$$ \Omega(M_n \cdot n). $$

For the upper bound, each execution of Algorithm V between two consecutive visits performs $O(1)$ structural updates of the controlling variables and at most one interchange operation per step of the underlying plain-change mechanism. Since each output is produced after a single visit step in Algorithm V, the amortized cost per generated permutation is $O(n)$ due only to the cost of maintaining and applying adjacent interchanges to an array of length $2n$.

Multiplying by the number of feasible outputs yields the total running time

$$ T(n) = \Theta(M_n \cdot n) = \Theta!\left(\frac{(2n)!}{2^n n!}, n\right). $$

This completes the proof. ∎