Multiset
Uit Wikipedia, de vrije encyclopedie
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 één 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 een zelfde 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 contrast met tupels, is de volgorde van elementen in multisets niet van belang. De onderstaande drie voorbeelden illustreren de verschillen tussen de concepten: (merk op dat een multiset ook kan worden beschouwd als een ongeordende tupel)
- 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 staat. Hoevaak 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. Gebruikelijk is het een multiset 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}.
Inhoud |
[bewerk] Definitie
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.
[bewerk] Formele notatie
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)}.
[bewerk] 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.
[bewerk] Referenties
- ^ Knuth, Donald E., The Art of Computer Programming - Vol. 2: Seminumerical Algorithms, 3e editie, Addison Wesley, 1998, p. 694 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).
- ^ Syropoulos, Apostolos (2001), p. 347.
