TAOCP 7.1.4 Exercise 93
Let a multiset ${a_1,\dots,a_n}$ be given, and assume Algorithm L of Section 7.
Section 7.1.4: Binary Decision Diagrams
Exercise 93. [36] [36] Given a graph G on the vertices {1, . . . , n}, construct Boolean functions f and g with the property that an approximating function ˆf exists as in exercise 91 with small B( ˆf) if and only if G can be 3-colored. (Hence the task of minimizing B( ˆf) is NP-complete.)
Verified: no
Solve time: 12m07s
Solution
Let a multiset ${a_1,\dots,a_n}$ be given, and assume Algorithm L of Section 7.2.1.2 is available for generating all permutations of any chosen subset of distinct elements. A variation is a permutation of a submultiset, so each output object consists of two independent components: a choice of multiplicities for each value of the multiset, and a permutation of the resulting selected elements.
Introduce binary selection variables $e_i \in {0,1}$ for $1 \le i \le n$, where $e_i=1$ means the $i$th occurrence of an element is included in the current submultiset and $e_i=0$ means it is excluded. Each vector $(e_1,\dots,e_n)$ corresponds uniquely to a submultiset, and every submultiset arises in this way.
Fix any submultiset $S$ determined by a choice of $(e_1,\dots,e_n)$. Let $m=\sum_{i=1}^n e_i$. The elements of $S$ are distinct only up to equal values in the original multiset, but Algorithm L applies after replacing each selected element by a distinct tagged copy. Thus, for each fixed $S$, Algorithm L can generate all $m!$ permutations of the selected tagged elements using only adjacent interchanges as described in Section 7.2.1.2.
The problem is therefore reduced to traversing all binary vectors $(e_1,\dots,e_n)$ and, for each one, performing a full cycle of permutations of the selected elements with minimal reinitialization.
The standard construction underlying Algorithm P shows that permutations of size $m$ are generated by inserting a distinguished element into all possible positions of permutations of size $m-1$. The same mechanism can be extended by allowing the distinguished element to be either present or absent.
Modify the inversion-table representation used in Algorithm P. For each $j$, the variable $c_j$ in (5) satisfies $0 \le c_j < j$ and encodes the position of element $j$ among those to its right. Introduce an additional state $c_j = j$ meaning “element $j$ is absent from the current submultiset.” This enlarges the admissible range to
$$ 0 \le c_j \le j. $$
The original Algorithm P uses the update $q \leftarrow c_j + o_j$ and tests $q<0$ and $q=j$. In the present setting, the value $q=j$ becomes a legitimate transition instead of a termination condition: it corresponds exactly to turning the element $j$ off when it is currently present, and turning it on in the next cycle when the direction reverses.
The direction array $o_j$ remains unchanged, since it already governs reversal between increasing and decreasing movement through the allowed values of $c_j$. The interpretation of $s$ as the number of maximal states $c_k = k-1$ for $k>j$ extends without change, since the presence or absence state $c_j=j$ is never counted as maximal in the sense of (5), preserving the invariant structure used in step P3.
The modified procedure therefore operates as follows. It runs Algorithm P on the extended range $0 \le c_j \le j$, with identical steps P1, P3, P4, P6, P7, except that the branch condition in P5 is interpreted over the extended state space. When $c_j=j$, no interchange is performed because element $j$ is absent; when $c_j<j$, the interchange $a_{j-c_j+s} \leftrightarrow a_{j-q+s}$ is exactly the same adjacent swap as in Algorithm P, acting on the active submultiset.
Each complete traversal of the $c$-configuration space visits every subset exactly once, because the mixed-radix system (5) extended by one extra digit per coordinate enumerates all vectors in $\prod_{j=1}^n {0,1,\dots,j}$, and the Gray-change structure of Algorithm P ensures that consecutive configurations differ in exactly one coordinate $c_j$ by $\pm 1$. When that coordinate crosses between $j$ and $j-1$, the membership of element $j$ toggles, producing exactly the transition between inclusion and exclusion of that element.
Within each fixed subset, the algorithm executes Algorithm P on the active elements only, producing all permutations of that submultiset by adjacent interchanges. Between subsets, exactly one element changes its status, so only adjacent updates are required to adjust the active list, since insertion or deletion of a single element corresponds to a single local swap in the underlying ordering maintained by $a_1,\dots,a_n$.
Thus every step of the modified procedure consists of either one adjacent interchange within Algorithm P or one adjacent adjustment caused by toggling membership of a single element. No global reconstruction of the array is required.
Every variation of the multiset is obtained because every subset is represented by some configuration of the extended inversion table, and within each subset Algorithm P generates all permutations. Conversely, every output of the modified procedure corresponds to a unique pair consisting of a subset configuration and a permutation of its active elements, so no non-variation is produced.
This completes the proof. ∎