TAOCP 7.1.4 Exercise 151
Algorithm J performs _sifting_ by repeatedly moving a chosen variable through all possible positions in the variable ordering, exchanging it with adjacent variables to minimize the BDD size.
Section 7.1.4: Binary Decision Diagrams
Exercise 151. [20] [20] Suggest a way to invoke Algorithm J so that each variable is sifted just once.
Verified: no
Solve time: 4m35s
Solution
Algorithm J performs sifting by repeatedly moving a chosen variable through all possible positions in the variable ordering, exchanging it with adjacent variables to minimize the BDD size. The cost of multiple invocations comes from revisiting variables after earlier sifts have changed the global structure.
To ensure that each variable is sifted just once, the invocation of Algorithm J is organized so that variables are processed in a single pass with permanent commitment after each sift.
Let the variables be $x_1, \dots, x_n$. Introduce a list $L$ containing all variables in some fixed or heuristically chosen initial order. The algorithm repeatedly removes the first variable of $L$, applies Algorithm J to sift that variable completely through all admissible positions, and then permanently fixes its position in the ordering. Once fixed, that variable is never reconsidered in subsequent sifts.
Formally, the invocation proceeds by selecting a variable $x_j$, executing Algorithm J on $x_j$ with respect to the current BDD ordering, and then declaring $x_j$ frozen. The remaining variables are then sifted only among the unfrozen positions, so the effect of earlier sifts cannot be undone.
This restriction ensures that each variable participates in exactly one complete sifting operation, since after completion of its invocation of Algorithm J it is excluded from further swaps. The ordering of remaining variables evolves only within the unfrozen subset, so no previously processed variable is reintroduced into any subsequent sift.
Correctness follows because each call to Algorithm J is unchanged in its local behavior: it still explores all positions for the chosen variable and selects the best placement according to the standard cost function. The modification lies only in the control structure of invocation, not in the internal mechanics of sifting.
Thus Algorithm J is applied exactly once per variable, and the final ordering is obtained after $n$ sifting operations, one per variable. This completes the construction. ∎