Partial orders for Counter data structures 0 ▲ Abstract Nonsense 110 days ago · Tech · hide · Fediverse post A counter data structure provides an abstract data type for a multiset. A multiset is much like a classic set, but augmented to track the multiplicity of each of its member elements. For example, $[1, 1, 1, 2, 3]$ is a multiset consisting of $1$ repeated thrice, and each of $2$ and $3$ once. If you define $A$ and $B$ to be multisets in a universe of objects $U$, and $m_A, m_B$ their respective multiplicity functions from $U\to \mathbb{N}$, you can define multiset inclusion as $$ A \subseteq B \iff \forall x \in U, \ m_A(x) \le m_B(x) $$The inclusion relation lets us define a partial order on multisets. Note that it is not a total order since it is not the case that any two multisets are comparable. For example, take $A=[1, 1, 2]$ and $B=[1, 2, 2]$. We have $m_A(1) = 2 > 1 = m_B(1)$ but $m_A(2) = 1 < 2 = m_B(2)$. Thus, neither multiset contains the other, and they are incomparable. You can define other arithmetic-like relations by delegating to their multiplicity functions in a similar… Commenting on Bubbles has been removed. Why? If you want to talk about this post, write to the author, use the comments on their blog if it has them, or reply with a "RE:" post on your own blog. Suggestions? feedback@bubbles.town