TAOCP 5.1.2 Exercise 9

Section 5.1.2: Permutations of a Multiset

Exercise 9. [33] [33] Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C.

Verified: no
Solve time: 20m23s

Exercise 5.1.2.9 [33]

9. Write computer programs that perform the factorizations of a given multiset permutation into the forms mentioned in Theorems A and C.

Solution

Let $M$ be a multiset of $n$ elements, possibly with repetitions. Let $\pi$ be a permutation of $M$, written in one-line notation as $\pi = a_1 a_2 \dots a_n$. We describe algorithms to compute:

The intercalation factorization of $\pi$ as in Theorem A.
The prime factorization of $\pi$ as in Theorem C.

We first recall the precise definitions from TAOCP:

Theorem A (Intercalation factorization). Every permutation of a multiset can be factored as

$$ \pi = \alpha_1 , \alpha_2 , \dots , \alpha_k, $$

where each $\alpha_i$ is an intercalation factor, that is, a permutation of a submultiset such that the sequence of intercalation factors satisfies a certain recursive decomposition: each $\alpha_i$ is minimal nonempty with respect to the property that its elements are all distinct from the union of the previous factors.

Theorem C (Prime factorization). Every permutation of a multiset can be uniquely expressed as a product of prime permutations (cycles) in which no cycle can be further decomposed as a product of nontrivial factors that commute with each other.

1. Algorithm for Intercalation Factorization (Theorem A)

The factorization of Theorem A is recursive. The first intercalation factor $\alpha_1$ is defined as the shortest prefix of $\pi$ such that its multiset contains no repeated element relative to $\alpha_1$ itself. Once $\alpha_1$ is determined, the remainder of $\pi$ is factored recursively.

We define the algorithm formally.

Algorithm IA: Intercalation Factorization

Input: A permutation $\pi = a_1 a_2 \dots a_n$ of a multiset $M$

Output: A list $\mathcal{F} = [\alpha_1, \alpha_2, \dots, \alpha_k]$ of intercalation factors

Initialize $\mathcal{F} \gets []$ and $i \gets 1$.
While $i \le n$:

a. Initialize an empty multiset $S \gets \emptyset$ and $j \gets i$.

b. While $a_j \notin S$:

i. Add $a_j$ to $S$.

ii. Increment $j \gets j + 1$.

c. Let $\alpha \gets a_i a_{i+1} \dots a_{j-1}$.

d. Append $\alpha$ to $\mathcal{F}$.

e. Set $i \gets j$. 3. Return $\mathcal{F}$.

Correctness:

At each step, we select the minimal prefix $\alpha$ starting at position $i$ that contains no repeated element. This matches the recursive construction in Theorem A.
By construction, the union of $\alpha_1, \dots, \alpha_k$ equals $\pi$, and each $\alpha_i$ is an intercalation factor.
The recursion ends when all elements of $\pi$ are assigned.

Complexity: $O(n)$ using a hash set to track elements in $S$.

2. Algorithm for Prime Factorization (Theorem C)

The prime factorization decomposes a permutation into cycles, where each cycle is prime: it cannot be split into commuting sub-permutations. For a multiset permutation, we identify cycles by tracing the action of $\pi$ on positions corresponding to repeated elements.

We adopt the standard cycle-finding procedure adapted to multisets:

Algorithm PC: Prime Cycle Factorization

Input: A permutation $\pi = a_1 a_2 \dots a_n$ of multiset $M$

Output: A list $\mathcal{P} = [\sigma_1, \dots, \sigma_m]$ of prime cycles

Initialize $\text{used} \gets \emptyset$, $\mathcal{P} \gets []$.
For each index $i \in {1, \dots, n}$:

a. If $i \in \text{used}$, continue to next $i$.

b. Initialize an empty list $\sigma \gets []$ and $j \gets i$.

c. Repeat:

i. Append $a_j$ to $\sigma$.

ii. Mark $j$ as used: $\text{used} \gets \text{used} \cup {j}$.

iii. Let $j \gets \text{position of } a_j \text{ in the multiset after applying } \pi$ (next image under $\pi$).

iv. Until $j \in \text{used}$.

d. Append $\sigma$ to $\mathcal{P}$. 3. Return $\mathcal{P}$.

Implementation Note:

To find "the position of $a_j$ in the multiset after applying $\pi$", maintain for each symbol a list of positions where it occurs. When constructing cycles, select the next unused occurrence of that symbol according to the one-line notation of $\pi$.
Each cycle $\sigma$ is prime because no proper nonempty subcycle commutes with the rest of the permutation: adding any element outside $\sigma$ would break the cycle closure.

Correctness:

Each element appears in exactly one cycle (disjointness).
Each cycle is maximal and cannot be split into commuting sub-permutations, satisfying the prime condition of Theorem C.
By iterating over all indices, all elements of $\pi$ are included.
The product of the cycles reproduces $\pi$, up to order of commuting cycles.

Complexity: $O(n)$ with proper bookkeeping of used indices.

3. Example

Let $\pi = a b a c b$.

Intercalation Factorization (Algorithm IA):

Start at $i=1$: $S=\emptyset$, read $a$ then $b$, then $a$ repeats → stop at $j=3$.

→ $\alpha_1 = a b$ 2. Start at $i=3$: $S=\emptyset$, read $a$, then $c$, then $b$ → end → $\alpha_2 = a c b$

Output: $\mathcal{F} = [a b, a c b]$

Prime Factorization (Algorithm PC):

Track positions: $a$ at positions 1,3; $b$ at 2,5; $c$ at 4.
Start at index 1 ($a_1 = a$): cycle $\sigma_1 = [a_1, a_3]$ → positions 1,3.
Next unused index 2 ($b_2$): cycle $\sigma_2 = [b_2, b_5]$.
Next unused index 4 ($c_4$): cycle $\sigma_3 = [c_4]$.

Output: $\mathcal{P} = [[a_1, a_3], [b_2, b_5], [c_4]]$

Each cycle is prime, disjoint, and reproduces $\pi$ under composition.

4. Remarks

The intercalation factorization captures the structure of Theorem A: each factor contains no element already used in previous factors.
The prime factorization captures Theorem C: cycles are maximal, disjoint, and cannot be further decomposed.
Both algorithms can be implemented efficiently in standard programming languages using hash tables or arrays for bookkeeping.
The output of Algorithm PC is unique up to reordering commuting cycles, consistent with Theorem C.

This completes the corrected solution.

∎