Section 7.2.1.2: Generating All Permutations

Exercise 9. [22] [22] Continuing the previous exercise, design an algorithm to generate all r- variations of a given multiset {a1, a2, . . . , an}, also called its r-permutations, namely all permutations of its r-element submultisets. (For example, the solution to an alphametic with r distinct letters is an r-variation of {0, 1, . . . , 9}.)

Verified: yes
Solve time: 4m27s

---

The failure in the previous solution is entirely caused by an inconsistent global state variable $t$. The correct fix is to eliminate any mutable “repair” of the residual sum and replace the outer enumeration with a direct invariant-driven construction of bounded compositions.

We restart the outer algorithm from first principles.

1. Correct formulation of the outer problem

We must generate all integer vectors

$$ x = (x_1,\dots,x_n) $$

such that

$$ \sum_{j=1}^n x_j = r,\qquad 0 \le x_j \le m_j. $$

This is a bounded composition problem.

Define for convenience the remaining capacity of suffix indices:

$$ M_{j} = \sum_{k=j}^n m_k. $$

At any prefix $x_1,\dots,x_j$, feasibility depends only on whether the remaining sum can still be completed:

$$ 0 \le r - \sum_{i=1}^j x_i \le M_{j+1}. $$

No auxiliary state variable is needed beyond the remaining sum.

2. Correct generation algorithm (lexicographic DFS)

We use a depth-first construction that maintains a single invariant:

At level $j$, we know:

$$ s = \sum_{i=1}^{j-1} x_i,\qquad r_{\mathrm{rem}} = r - s. $$

We choose $x_j$ and update the remaining sum consistently.

Algorithm V (bounded r-compositions)

Input: $m_1,\dots,m_n$, target $r$

Precompute:

$$ M_{j} = \sum_{k=j}^n m_k. $$

Procedure $F(j, r_{\mathrm{rem}})$

If $j = n+1$:

• If $r_{\mathrm{rem}} = 0$, output $x_1,\dots,x_n$
• Return

Otherwise:

Compute feasible bounds:

$$ L_j = \max\bigl(0,, r_{\mathrm{rem}} - M_{j+1}\bigr), \qquad U_j = \min(m_j,, r_{\mathrm{rem}}). $$

For each value

$$ x_j = L_j, L_j+1, \dots, U_j: $$

do:

• set $x_j$
• call

$$ F(j+1, r_{\mathrm{rem}} - x_j). $$

Initialization

Call:

$$ F(1, r). $$

3. Why the previous algorithm failed

The earlier solution attempted to maintain a global variable $t$ with ad hoc corrections during backtracking. That introduced two fatal issues:

• $t$ was modified using stale values of $x_k$, breaking the identity $t = r - \sum x_i$
• backtracking did not correspond to any invariant-preserving traversal of the solution space

In contrast, the recursive formulation enforces the invariant by construction:

$$ r_{\mathrm{rem}} = r - \sum_{i=1}^{j-1} x_i $$

is always exact, never repaired.

4. Correctness of the outer enumeration

Lemma 1 (Invariant correctness)

At every recursive call $F(j, r_{\mathrm{rem}})$,

$$ r_{\mathrm{rem}} = r - \sum_{i=1}^{j-1} x_i. $$

Proof is immediate by induction:

• Base: $F(1,r)$ holds.
• Step: after choosing $x_j$, we pass $r_{\mathrm{rem}} - x_j$, preserving the identity.

Lemma 2 (Feasibility of bounds)

The range

$$ L_j = \max(0, r_{\mathrm{rem}} - M_{j+1}), \quad U_j = \min(m_j, r_{\mathrm{rem}}) $$

is exactly the set of values of $x_j$ that allow completion.

Proof:

• Upper bound ensures $x_j \le m_j$ and nonnegativity of remainder.
• Lower bound ensures remaining demand $r_{\mathrm{rem}} - x_j$ does not exceed total suffix capacity $M_{j+1}$.

Thus:

$$ r_{\mathrm{rem}} - x_j \le M_{j+1}. $$

Lemma 3 (Completeness)

Let $x$ be any feasible solution. Then at each level $j$,

$$ x_j \in [L_j, U_j], $$

so the recursion will follow exactly the branch selecting $x_j$. Hence every feasible vector is generated.

Lemma 4 (No repetition)

Each vector $x$ corresponds to a unique path in the recursion tree, determined by its coordinate sequence. Since recursion enumerates each branch once, no duplication occurs.

Lemma 5 (Termination)

The search tree is finite because:

$$ 0 \le x_j \le m_j, $$

so each level has finitely many branches and depth is $n$.

5. Inner permutation generation

For each valid multiplicity vector $x$, form the multiset

$$ A = {a_1^{x_1}, \dots, a_n^{x_n}}. $$

Apply Algorithm L (Knuth, Section 7.2.1.2), which generates all permutations of a multiset by adjacent transpositions, visiting each permutation exactly once.

Thus, for each $x$, all permutations of $A$ are produced exactly once.

6. Combined correctness

Define the set of $r$-variations:

$$ \mathcal{V} = \bigcup_{\substack{x_1+\cdots+x_n=r \ 0 \le x_j \le m_j}} \mathrm{Perm}(x_1,\dots,x_n). $$

The algorithm produces:

• every feasible $x$ exactly once (by Lemmas 3 and 4)
• every permutation of each $x$ exactly once (Algorithm L)

Hence there is a bijection:

$$ (x,\pi) \longleftrightarrow \text{generated output}. $$

Therefore every $r$-variation is generated exactly once.

Final conclusion

The corrected solution replaces the flawed global backtracking state with a strict recursive invariant-based enumeration of bounded compositions. This restores correctness of feasibility bounds, eliminates state corruption, and yields a complete and non-redundant generation of all $r$-variations of the multiset.