Multiset

Uit Wikipedia, de vrije encyclopedie
Ga naar: navigatie, zoeken

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

Het totale aantal elementen in een multiset, inclusief herhaald lidmaatschap, wordt de kardinaliteit van een multiset genoemd, en het aantal keren dat eenzelfde lid voorkomt in een multiset, wordt de multipliciteit van dat lid genoemd. In de multiset {a, a, b, b, b, c} is de multipliciteit van de leden a, b, en c respectievelijk 2, 3, en 1, en de kardinaliteit van de multiset 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) zijn niet gelijk, aangezien in tupels de volgorde van belang is; en de tupels (a, a) en (a) zijn niet gelijk, omdat in tupels en multisets de multipliciteit van belang is, waardoor de kardinaliteit verschilt.
  • De multisets {a, b} en {b, a} zijn gelijk, omdat in multisets de volgorde niet van belang is, maar de multisets {a, a} en {a} zijn niet gelijk, aangezien zij verschillende kardinaliteiten hebben.
  • De verzamelingen {a, b} en {b, a} zijn gelijk, net als de multisets {a, b} en {b, a}; maar hoewel de verzamelingen {a, a} en {a} zijn gelijk, geldt dit niet voor de multisets {a, a} en {a}, dit omdat in verzamelingen het concept van multipliciteit geen rol speelt. Hoe vaak een element deel uitmaakt van een verzameling speelt geen rol, het element telt in een verzameling maar één keer mee.

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}.

Wanneer de elementen van een multiset worden genummerd, ontstaat een (genummerde) rij. De volgorde van de elementen is dan wel belangrijk.

Definitie[bewerken]

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.

Formele notatie[bewerken]

Een formele manier om een multiset (V,m) te noteren is: {(v,m(v)): v ∈ V }, dus als 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[bewerken]

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.

Referenties[bewerken]

  1. Knuth, Donald E., The Art of Computer Programming - Vol. 2: Seminumerical Algorithms, 3e editie, Addison Wesley, 1998, p. 694 ISBN 0201896842. Knuth geeft in zijn boek ook andere namen voor multisets, zoals list (lijst), bunch (bundel), bag (tas), heap (stapel), sample (staal), weighted set (gewogen verzameling), collection (collectie), suite (stel).
  2. Syropoulos, Apostolos (2001), p. 347.