Multiset

In de wiskunde is een multiset (uit het Engels: multiset of bag (zak)) een generalisatie van het concept verzameling. Een element van een multiset kan meer dan één keer in de multiset voorkomen, dit in tegenstelling tot een verzameling, waarin elk element precies één keer voorkomt. De term "multiset" werd in de jaren zeventig van de twintigste eeuw geïntroduceerd door Nicolaas Govert de Bruijn. Het gebruik van multisets in wiskunde gaat echter vooraf aan de introductie van de term 'multiset'. In 1888 gebruikte Richard Dedekind het concept al in een van zijn artikelen.

Het aantal keren dat eenzelfde element voorkomt in een multiset, wordt de multipliciteit van dat element genoemd. In de multiset {a, a, b, b, c, b} bijvoorbeeld is de multipliciteit van de elementen a, b en c respectievelijk 2, 3 en 1.

Het totale aantal elementen in een multiset is de som van de multipliciteiten van de elementen en wordt de kardinaliteit van de multiset genoemd. De kardinaliteit van de multiset {a, a, b, b, c, b} is 6.

Net als in verzamelingen, maar in tegenstelling tot tupels, is de volgorde van elementen in multisets niet van belang. De onderstaande drie voorbeelden illustreren de verschillen tussen de concepten:

• De tupels (a, b) en (b, a), met a ≠ b, zijn niet aan elkaar gelijk, aangezien in tupels de volgorde van belang is; ook de tupels (a, a) en (a) zijn niet aan elkaar gelijk, omdat in tupels en multisets de multipliciteit van belang is, waardoor de kardinaliteit verschilt.
• De multisets {a, b} en {b, a} zijn aan elkaar gelijk, omdat in multisets de volgorde niet van belang is, maar de multisets {a, a} en {a} zijn niet dezelfde, aangezien zij verschillende kardinaliteiten hebben. Wel zijn de verzamelingen {a, a} en {a} aan elkaar gelijk.
• De verzamelingen {a, b} en {b, a} zijn aan elkaar gelijk, net als de multisets {a, b} en {b, a}.

Er is geen eenduidige notatie voor een multiset. Het is gebruikelijk een multiset als zodanig te benoemen en te noteren als een verzameling en de gelijke elementen te herhalen. Een eenvoudig voorbeeld van een multiset is: {1,2,2,2,3,3}, met de elementen 1 met multipliciteit 1, 2 met multipliciteit 3 en 3 met multipliciteit 2. Men dient te weten dat het hier om een multiset gaat, want als verzameling opgevat geldt: {1,2,2,2,3,3} = {1,2,3}.

Definitie en notatie

Een multiset is een paar (V,m), waarin V een verzameling is en m een afbeelding die aan elk element v van V een natuurlijk getal, m(v), de multipliciteit van v, toevoegt. Gezien de definitie van afbeelding en tweeplaatsige relatie is een multiset (V,m) dus te noteren als {(v,m(v)): v ∈ V }, de verzameling paren van de elementen van v met hun multipliciteit.

Voorbeeld: de multiset {a,b,b,b,c,c}, met a, b en c verschillend, wordt formeel genoteerd als: {(a,1),(b,3),(c,2)}.

Informatica

In de informatica is een multiset een bepaald type container, en wordt dan meestal een bag genoemd.

Om, ten opzichte van een verzameling, de dubbele elementen mogelijk te maken kent men aan elk (uniek) element een multipliciteit toe. Zo'n paar van element en multipliciteit heet een tupel. Het koppelen van een element aan zijn multipliciteit heet tupelen. Het is voor de hand liggend een bag te implementeren als een associatieve array van integers.