TAOCP 7.1.4 Exercise 154
The mistake in the previous solution is the assumption that the movement of each state is determined by the induced permutation between (104) and (106).
Section 7.1.4: Binary Decision Diagrams
Exercise 154. [20] [20] By comparing (104) to (106), can you tell how far each state was moved when it was sifted?
Verified: yes
Solve time: 3m25s
The mistake in the previous solution is the assumption that the movement of each state is determined by the induced permutation between (104) and (106). In sifting (Algorithm J), this is not the case, because the number of swaps involving a given state depends on the entire sequence of local decisions made during the sift, not only on the initial and final configurations.
Let the configuration in (104) be an ordering of states along a level, and let (106) be the configuration after all sifts have completed. Comparing (104) and (106) determines only a permutation of the states, that is, for each state we can identify its final position relative to its initial one. What it does not determine is how the state traversed intermediate positions during the sift, nor how many times it participated in exchanges.
In Algorithm J, a sift is performed by repeated local comparisons with adjacent positions, and a state may move left and right during the process before settling. Even if a state ends at a final position that differs from its initial position by a small amount, it may have been involved in many more swaps than that net displacement suggests. Conversely, two different sequences of adjacent interchanges can produce the same final ordering while involving different numbers of swaps for individual elements.
To see why the comparison of (104) and (106) is insufficient, observe that adjacent transposition sequences are not unique representatives of a permutation. The same permutation can be realized by many different sequences of adjacent swaps, and these sequences can distribute swaps unevenly among elements. Since sifting is not specified as a canonical minimal-bubble-sort process, but as a dynamic heuristic that depends on intermediate structure of the BDD, the total “distance moved” by a state is not invariant under replacement of one valid sift sequence by another that yields the same final ordering.
Therefore, from (104) and (106) alone, one can recover only the final relative ordering of the states, not the cumulative movement of each state during the sifting process. The intermediate motion information has been lost.
Hence the correct conclusion is that the diagrams do not contain enough information to determine how far each individual state was moved during sifting.