========
multiset
========
.. toctree::
:hidden:
:titlesonly:
Overview
api
This package provides a multiset_ implementation for Python.
A multiset is similar to the builtin :class:`set`, but it allows an element to occur multiple times.
It is an unordered collection of element which have to be :term:`python:hashable` just like in a :class:`set`.
It supports the same :ref:`methods and operations ` as :class:`set` does, e.g. membership test,
:meth:`union `, :meth:`intersection `, and
(:meth:`symmetric `) :meth:`difference `. Multisets can be used in
combination with regular sets for those operations.
The implementation is based on a :class:`dict` that maps the elements to their multiplicity in the multiset.
Hence, some :ref:`dictionary operations ` are supported.
In contrast to the :class:`collections.Counter` from the standard library, it has proper support for set
operations and only allows positive counts. Also, elements with a zero multiplicity are automatically
removed from the multiset.
There is an immutable version of the multiset called :class:`FrozenMultiset`.
The package also uses the :mod:`typing` module for type hints (see :pep:`484`) so you can specify the type of a
multiset like ``Multiset[ElementType]``.
API Overview
------------
The following is an overview over the methods of the :class:`Multiset` class. For more details on each method and some
examples see the autogenerated :doc:`api`.
.. class:: Multiset([mapping or iterable])
Return a new multiset object whose elements are taken from
the given optional iterable or mapping. If a mapping is given, it must have positive `int`
values representing each element's multiplicity. If no iterable or mapping is specified, a new empty multiset is
returned.
The elements of a set must be :term:`python:hashable`. In contrast to regular sets, duplicate elements
will not be removed from the multiset.
.. _SetMethods:
The :class:`Multiset` class provides the following operations which the builtin :class:`set` also supports:
.. describe:: len(s)
Return the total number of elements in multiset *s* (cardinality of *s*).
Note that this is the sum of the multiplicities and not not the number of distinct elements.
You can use :meth:`distinct_elements` to get the number of distinct elements::
>>> len(Multiset('aab').distinct_elements())
2
.. describe:: x in s
Test *x* for membership in *s*.
.. describe:: x not in s
Test *x* for non-membership in *s*.
.. method:: isdisjoint(other)
Return ``True`` if the multiset has no elements in common with *other*.
.. method:: issubset(other)
multiset <= other
Test whether every element in the multiset is in *other* and each element's multiplicity in the
multiset is less than or equal to its multiplicity in *other*.
.. method:: multiset < other
Test whether the multiset is a proper subset of *other*, that is,
``multiset <= other and multiset != other``.
.. method:: issuperset(other)
multiset >= other
Test whether every element in *other* is in the multiset and each element's multiplicity in *other*
is less than or equal to its multiplicity in the multiset.
.. method:: multiset > other
Test whether the multiset is a proper superset of *other*, that is, ``multiset >=
other and multiset != other``.
.. method:: union(*others)
multiset | other | ...
Return a new multiset with elements from the multiset and all others. The maximal multiplicity over all
sets is used for each element.
.. method:: combine(*others)
multiset + other + ...
Return a new multiset with elements from the multiset and all others. Each element's multiplicities are summed
up for the new set.
.. method:: intersection(*others)
multiset & other & ...
Return a new multiset with elements common to the multiset and all others. The minimal multiplicity over all
sets is used for each element.
.. method:: difference(*others)
multiset - other - ...
Return a new multiset with elements in the multiset that are not in the others. This will subtract all the *others'*
multiplicities and remove the element from the multiset if its multiplicity reaches zero.
.. method:: symmetric_difference(other)
multiset ^ other
Return a new multiset with elements from either the multiset or *other* where their multiplicity is the absolute
difference of the two multiplicities.
.. method:: copy()
Multiset(multiset)
Return a new shallow copy of the multiset.
The following methods are not supported by :class:`FrozenMultiset`, as it is equivalent to the builtin
:class:`frozenset` class and is immutable:
.. method:: union_update(*others)
multiset |= other | ...
Update the multiset, adding elements from all others. The maximal multiplicity over all
sets is used for each element.
For a version of this method that works more closely to :meth:`dict.update`, see :meth:`update`.
.. method:: intersection_update(*others)
multiset &= other & ...
Update the multiset, keeping only elements found in it and all others. The minimal multiplicity over all
sets is used for each element.
.. method:: difference_update(*others)
multiset -= other | ...
Update the multiset, removing elements found in others. This will subtract all the *others'*
multiplicities and remove the element from the multiset if its multiplicity reaches zero.
.. method:: symmetric_difference_update(other)
multiset ^= other
Update the multiset, keeping only elements found in either the multiset or *other* but not both.
The new multiplicity is the absolute difference of the two original multiplicities.
.. method:: add(element, multiplicity=1)
s[element] += multiplicity
s[element] = multiplicity
Add element *element* to the multiset *s*. If the optional multiplicity is specified, more than one
element can be added at the same time by adding to its.
Note that adding the same element multiple times will increase its multiplicity and thus change the multiset,
whereas for a regular :class:`set` this would have no effect.
You can also set the element's multiplicity directly via key assignment.
.. method:: remove(element, multiplicity=None)
del s[element]
Remove all elements *element* from the multiset. Raises :exc:`KeyError` if *element* is
not contained in the set.
If the optional multiplicity is specified, only the given
number is subtracted from the element's multiplicity. This might still completely remove
the element from the multiset depending on its original multiplicity.
This method returns the original multiplicity of the element before it was removed.
You can also delete the element directly via key access.
.. method:: discard(element, multiplicity=None)
s[element] -= multiplicity
s[element] = 0
Remove element *element* from the set if it is present. If the optional multiplicity is specified, only the given
number is subtracted from the element's multiplicity. This might still completely remove
the element from the multiset depending on its original multiplicity.
This method returns the original multiplicity of the element before it was removed.
You can also set the element's multiplicity directly via key assignment.
.. method:: clear()
Remove all elements from the multiset.
Note, the non-operator versions of :meth:`union`, :meth:`intersection`,
:meth:`difference`, and :meth:`symmetric_difference`, :meth:`issubset`, and
:meth:`issuperset`, :meth:`update`,
:meth:`intersection_update`, :meth:`difference_update`, and
:meth:`symmetric_difference_update` methods will accept any iterable as an argument. In
contrast, their operator based counterparts require their arguments to be
sets. This precludes error-prone constructions like ``Multiset('abc') & 'cbs'``
in favor of the more readable ``Multiset('abc').intersection('cbs')``.
The :class:`Multiset` supports set to set comparisons. Two
multisets are equal if and only if every element of each multiset is contained in the
other and each element's multiplicity is the same in both multisets (each is a subset
of the other). A multiset is less than another set if and
only if it is a proper subset of the second set (is a subset, but
is not equal). A multiset is greater than another set if and only if it
is a proper superset of the second set (is a superset, but is not equal).
These comparisons work with both sets and multisets::
>>> Multiset('ab') == {'a', 'b'}
True
Multiset elements, like set elements and dictionary keys, must be :term:`hashable`.
Binary operations that mix :class:`set` or :class:`frozenset` instances with
:class:`Multiset` instances will always return a :class:`Multiset`.
.. _DictMethods:
Since the :class:`Multiset` internally uses a :class:`dict`, it exposes some of its methods
and allows key-based access for elements:
.. describe:: s[element]
Return the multiplicity of *element* in *s*. Returns ``0`` for elements that are not
in the multiset.
.. describe:: s[element] = value
Set the multiplicity of *element* to *value*. Setting the multiplicity to ``0`` removes the element.
This is not supported by :class:`FrozenMultiset`.
.. describe:: del s[element]
See :meth:`remove`. This is not supported by :class:`FrozenMultiset`.
.. describe:: iter(s)
Return an iterator over the elements in the multiset.
In contrast to both the :class:`dict` and :class:`set` implementations, this will repeat elements
whose multiplicity is greater than ``1``::
>>> sorted(Multiset('aab'))
['a', 'a', 'b']
To only get distinct elements, use the :meth:`distinct_elements` method.
.. classmethod:: from_elements(elements, multiplicity)
Create a new multiset with elements from *elements* and all multiplicities set to *multiplicity*.
.. method:: get(element, default)
Return the multiplicity for *element* if it is in the multiset, else *default*.
.. method:: items()
Return a new view of the multiset's items (``(element, multiplicity)`` pairs).
See the :ref:`documentation of dict view objects `.
Note that this view is unordered.
.. method:: distinct_elements()
keys()
Return a new view of the multiset's distinct elements. See the :ref:`documentation
of dict view objects `.
Note that this view is unordered.
.. method:: update(*others)
multiset += other + ...
Update the multiset, adding elements from all others. Each element's multiplicities is summed up for the new multiset.
This is not supported by :class:`FrozenMultiset`.
For a version of this method that works more closely to the original :meth:`set.update`, see :meth:`union_update`.
.. method:: pop(element, default)
If *element* is in the multiset, remove it and return its multiplicity, else return
*default*.
This is not supported by :class:`FrozenMultiset`.
.. method:: popitem()
Remove and return an arbitrary ``(element, multiplicity)`` pair from the multiset.
This is not supported by :class:`FrozenMultiset`.
:meth:`popitem` is useful to destructively iterate over a multiset.
If the multiset is empty, calling :meth:`popitem` raises a :exc:`KeyError`.
.. method:: setdefault(element, default)
If *element* is in the multiset, return its multiplicity. If not, insert *element*
with a multiplicity of *default* and return *default*.
This is not supported by :class:`FrozenMultiset`.
.. method:: multiplicities()
values()
Return a new view of the multiset's multiplicities. See the
:ref:`documentation of dict view objects `.
Note that this view is unordered.
The multiset also adds some new methods for multiplying a multiset with an :class:`int` factor:
.. method:: times(factor)
multiset * factor
Return a copy of the multiset where each multiplicity is multiplied by *factor*.
.. method:: times_update(factor)
multiset *= factor
Update the multiset, multiplying each multiplicity with *factor*.
This is not supported by :class:`FrozenMultiset`.
.. class:: FrozenMultiset([mapping or iterable])
This is an immutable version of the :class:`Multiset` and supports all non-mutating methods of it.
Because it is immutable, it is also :term:`hashable` and can be used e.g. as a dictionary key or in a set.
.. class:: BaseMultiset
This is the base class of both :class:`Multiset` and :class:`FrozenMultiset`. While it cannot instantiated directly,
it can be used for isinstance checks:
>>> isinstance(Multiset(), BaseMultiset)
True
>>> isinstance(FrozenMultiset(), BaseMultiset)
True
.. _multiset: https://en.wikipedia.org/wiki/Multiset