TAOCP 3.4.2 Exercise 12

**Exercise 3.

taocpmathematicsalgorithmsvolume-2

Section 3.4.2: Random Sampling and Shuffling

Exercise 12. [**] [M36] The gist of Algorithm P is that any permutation $\pi$ can be uniquely written as a product of transpositions in the form $\pi = (a_1 t) \cdots (a_2 2)(a_1 2)$, where $1 \le a_j \le j$ for $1 \ge j > 1$. Prove that there is also a unique representation of the form $\pi = (b_t 2)(b_{t-1} 3) \cdots (b_1 t)$, where $1 \le b_j \le j$ for $1 < j \le t$, and design an algorithm that computes the $b$'s from the $a$'s in $O(t)$ steps.

Verified: no
Solve time: 4m34s

Exercise 3.4.2.12 [M36]

Solution.

We are asked to prove that if a permutation $\pi \in S_t$ is written in Algorithm P form

$$ \pi = (a_t, t) (a_{t-1}, t-1) \cdots (a_2, 2)(a_1,1), \quad 1 \le a_j \le j, $$

then $\pi$ also has a unique representation of the form

$$ \pi = (b_t,2)(b_{t-1},3)\cdots (b_1, t), \quad 1 \le b_j \le j, $$

and to give an $O(t)$-time algorithm to compute the $b$'s from the $a$'s.

We proceed in precise steps.

Step 1: Restate the original representation

By Algorithm P, any permutation $\pi \in S_t$ is uniquely represented as

$$ \pi = (a_t, t) (a_{t-1}, t-1) \cdots (a_2, 2) (a_1,1), $$

with $1 \le a_j \le j$. The factor $(a_1,1)$ is always trivial $(1,1)$, so we may ignore it. Then we have

$$ \pi = (a_t, t) (a_{t-1}, t-1) \cdots (a_2, 2). $$

Our goal is to rewrite this in the reverse-indexed form

$$ \pi = (b_t, 2)(b_{t-1}, 3)\cdots (b_2, t)(b_1,1), $$

or equivalently (ignoring $(b_1,1)$),

$$ \pi = (b_t,2)(b_{t-1},3)\cdots (b_2, t). $$

Notice that the factors now attach to positions $2,3,\dots,t$ in increasing order, with $b_j \le j$.

Step 2: Strategy for existence

The key observation is that Algorithm P defines a factorial-number representation of permutations: for each $j$, the transposition $(a_j,j)$ inserts the element $j$ into position $a_j$ in the growing permutation $[1,\dots,j]$.

Similarly, to produce the representation

$$ \pi = (b_t,2)(b_{t-1},3)\cdots (b_2,t), $$

we will insert each symbol $j$ at position $b_{t-j+2}$ in the partially constructed permutation, but now proceeding in reverse order. Concretely:

  1. Start with the identity permutation $\sigma_1 = [1]$.
  2. For $j = 2$ to $t$, define $b_{t-j+2}$ so that swapping positions $b_{t-j+2}$ and $j$ in the current sequence correctly inserts $j$ at its position according to the permutation $\pi$.

Equivalently, we can view the mapping from $a$-indices to $b$-indices as reindexing the factorial representation in reverse.

Step 3: Inductive construction

Let us define the sequence $(b_2,\dots,b_t)$ inductively. Let $\pi^{(j)} = (a_j, j) (a_{j-1}, j-1) \cdots (a_2,2)$ denote the partial product of the first $j-1$ factors from the original Algorithm P form. We want

$$ \pi^{(j)} = (b_j,2)(b_{j-1},3)\cdots (b_2, j). $$

Then $b_j$ is determined as follows:

$$ b_j = \text{the image of } j \text{ under the inverse of the partial product of the previous } b\text{-transpositions}. $$

Formally, if we let

$$ \beta_{j-1} = (b_{j-1},2)(b_{j-2},3)\cdots (b_2, j-1), $$

then define

$$ b_j = \beta_{j-1}^{-1}(j). $$

This guarantees that

$$ (b_j, j) \beta_{j-1} = \pi^{(j)}. $$

Hence by induction, each $b_j$ is uniquely determined, and existence is established.

Step 4: Uniqueness

To prove uniqueness, observe:

  1. The final transposition $(b_t,2)$ moves $t$ to its position in $\pi$. Since positions are distinct, $b_t$ is uniquely determined.
  2. Once $b_t$ is fixed, the next transposition $(b_{t-1},3)$ must move $t-1$ to its position in the partial permutation. Again, $b_{t-1}$ is uniquely determined.
  3. Proceeding inductively, each $b_j$ is uniquely determined by $\pi$.

Therefore the representation

$$ \pi = (b_t,2)(b_{t-1},3)\cdots (b_2, t) $$

is unique.

Step 5: Algorithm to compute $b_j$ from $a_j$

We can compute the $b$'s in $O(t)$ steps using an array $p[1..t]$ representing the current permutation of positions.

Idea: Let $p[k]$ track the element currently at position $k$. Initially, $p[k] = k$. Each transposition $(x,y)$ swaps $p[x]$ and $p[y]$.

Algorithm:

Input: a[2..t]  # Algorithm P indices
Output: b[2..t] # Reindexed representation

# Initialize identity permutation
for i = 1 to t:
    p[i] = i

# Compute b-values in increasing j
for j = 2 to t:
    # Find position of j in current partial permutation
    for k = 2 to j:
        if p[k] == j:
            b[j] = k
            break
    # Swap to apply the transposition (b[j] j)
    swap p[b[j]] and p[j]

Explanation:

  • At iteration $j$, $p$ represents the partial permutation constructed so far from the $b$-transpositions.
  • $b[j]$ is chosen so that $(b[j],j)$ moves $j$ to its correct position according to $\pi$.
  • Swapping $p[b[j]]$ and $p[j]$ updates $p$ to include the new transposition.

Each outer iteration performs $O(1)$ work if we maintain positions in a separate array for constant-time lookup. Therefore, the total complexity is $O(t)$.

Step 6: Summary

  1. Existence: Define $b_j = \beta_{j-1}^{-1}(j)$, where $\beta_{j-1}$ is the partial product of previous $b$-transpositions.
  2. Uniqueness: Each $b_j$ is uniquely determined from $\pi$ by induction on $j$.
  3. Algorithm: Maintain a permutation array to compute $b_j$ and update by swapping, yielding an $O(t)$-time procedure.

This completes the solution.

∎

Pseudocode (compact $O(t)$ version with position array for constant-time lookup):

Input: a[2..t]
Output: b[2..t]

# Initialize identity permutation and inverse position array
for i = 1 to t:
    p[i] = i
    pos[i] = i

for j = 2 to t:
    b[j] = pos[j]           # position of j in current permutation
    swap p[b[j]] and p[j]   # apply transposition (b[j] j)
    pos[p[b[j]]] = b[j]     # update position of swapped element
    pos[p[j]] = j

This correctly computes the unique sequence $(b_2,\dots,b_t)$ corresponding to the permutation $\pi$ represented by $(a_2,\dots,a_t)$.