Multisetoperaties
Multisetoperaties zijn bewerkingen op multisets (ook wel bags genoemd), een generalisatie van verzamelingen waarbij elementen meerdere keren kunnen voorkomen. Een multiset A over een grondverzameling U wordt vaak beschreven door de multipliciteit m_A(x) van elk element x in U, dat is het aantal keren dat x in A voorkomt. Alleen elementen met positieve multipliciteit treden op in A. Als m_A(x) = 0 geldt, ontbreekt x in A.
De belangrijkste operaties op multisets zijn:
- Unie: m_{A ∪ B}(x) = max(m_A(x), m_B(x)). De eenheden komen samen zodat het hoogste voorkomen van elk element
- Doorsnede: m_{A ∩ B}(x) = min(m_A(x), m_B(x)). Het aantal voor x is het minimum van beide multipliciteiten.
- Multiset-som (disjunkte optelling): m_{A ⊎ B}(x) = m_A(x) + m_B(x). De multipliciteiten worden opgeteld.
- Verschil: m_{A \ B}(x) = max(m_A(x) − m_B(x), 0). Verwijdert de multipliciteit van B uit A.
- Symmetrische verschil: m_{A △ B}(x) = |m_A(x) − m_B(x)|. De verschillen in multipliciteit worden behouden.
Een multiset is een gewone collectie als alle multipliciteiten beperkt zijn tot 0 of 1. Multisetoperaties komen