TAOCP 7.1.4 Exercise 255
A multifamily $f$ assigns to each set $\alpha$ a multiplicity $m_f(\alpha) \in \mathbb{N}$.
Section 7.1.4: Binary Decision Diagrams
Exercise 255. ▶ [25] [25] A multifamily of sets, in which members of f are allowed to occur more than once, can be represented as a sequence of ZDDs (f0, f1, f2, . . . ) in which fk is the family of sets that occur ( . . . a2a1a0)2 times in f where ak = 1. For example, if α appears exactly 9 = (1001)2 times in the multifamily, α would be in f3 and f0. a) Explain how to insert and delete items from this representation of a multifamily. b) Implement the multiset union h = f ⊎g for multifamilies.
Verified: no
Solve time: 1m20s
Solution
A multifamily $f$ assigns to each set $\alpha$ a multiplicity $m_f(\alpha) \in \mathbb{N}$. Writing $m_f(\alpha)$ in binary,
$$ m_f(\alpha) = \sum_{k \ge 0} a_k(\alpha),2^k,\qquad a_k(\alpha)\in{0,1}, $$
the representation $(f_0,f_1,f_2,\dots)$ encodes $f$ by
$$ \alpha \in f_k \iff a_k(\alpha)=1. $$
Each $f_k$ is a ZDD-represented family of sets.
All operations reduce to bitwise arithmetic on the binary multiplicities of each fixed set $\alpha$, performed simultaneously over all $\alpha$ via ZDD op