A multiset records a nonnegative integer multiplicity for each element of a set. A finite multiset has finite support and finite total multiplicity. Its cardinality is the sum of its multiplicities; its disjoint union with another multiset adds multiplicities. The hook lengths of a Young diagram form a multiset, since different cells can have equal lengths.
A multiset of keys in a fixed finite integer range represented by one nonnegative count per key. The abstraction function extends the stored array counts by zero outside the range. Single-key additions, removals and queries use constant array work, provided overflow and operation preconditions are handled. Encapsulation of the count array is necessary to preserve its representation invariant.
Maintain a counter equal to the number of positive count-array entries. Increment it only when an addition changes zero to one; decrement it only when a removal changes one to zero. Other count changes leave the support unchanged. Initialization at zero and these cases prove the representation invariant by induction over completed operations, giving a constant-time distinct-size query.
The set of keys with positive multiplicity. Its cardinality counts distinct keys, whereas summing the multiplicities counts all occurrences. A count-array implementation can maintain the support cardinality by tracking only zero-to-positive and positive-to-zero transitions.
A finitely supported function , allowing negative as well as positive multiplicities. Missing keys denote zero. Addition, exact subtraction, pointwise maximum/minimum and pointwise order can be implemented over the union of operand supports. A nonnegative multiset is a refinement, but exact subtraction can leave that refinement while still producing a signed multiset. Fixed-width count implementations must also specify overflow behavior.
The common multiplicity of two multisets, summing the smaller multiplicity of each value. To return an order-preserving overlap of two finite lists, scan the first list and consume one equal item from the second whenever available. Each token can be consumed at most once, so the resulting subsequence has maximum possible length among those that occur in a permutation of the second list.
Articles by others on the same topic
A **multiset**, also known as a bag, is a generalization of a set that allows for multiple occurrences of the same element. In a standard set, each element can appear only once—meaning that sets are collections of distinct objects. In contrast, a multiset can contain the same element more than once, and each element is associated with a count representing its number of occurrences.