API Documentation

This page is automatically generated from the docstrings.

An implementation of a multiset.

class multiset.BaseMultiset(iterable=None)

Bases: object

A multiset implementation.

A multiset is similar to the builtin set, but elements can occur multiple times in the multiset. It is also similar to a list without ordering of the values and hence no index-based operations.

The multiset internally uses a dict for storage where the key is the element and the value its multiplicity. It supports all operations that the set supports.

In contrast to the builtin collections.Counter, no negative counts are allowed, elements with zero counts are removed from the dict, and set operations are supported.

The multiset comes in two variants, Multiset and FrozenMultiset which correspond to the set and frozenset classes, respectively.

Warning

You cannot instantiate this class directly. Use one of its variants instead.

See

https://en.wikipedia.org/wiki/Multiset

__init__(iterable=None)

Create a new, empty Multiset object.

And if given, initialize with elements from input iterable. Or, initialize from a mapping of elements to their multiplicity.

Example:

>>> ms = Multiset()                 # a new, empty multiset
>>> ms = Multiset('abc')            # a new multiset from an iterable
>>> ms = Multiset({'a': 4, 'b': 2}) # a new multiset from a mapping

Parameters

iterable – An optional iterable of elements or mapping of elements to multiplicity to initialize the multiset from.

combine(*others)

Return a new multiset with all elements from the multiset and the others with their multiplicities summed up.

>>> ms = Multiset('aab')
>>> sorted(ms.combine('bc'))
['a', 'a', 'b', 'b', 'c']

You can also use the + operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aab')
>>> sorted(ms + Multiset('a'))
['a', 'a', 'a', 'b']

For a variant of the operation which modifies the multiset in place see update().

Parameters

others – The other sets to add to the multiset. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

Returns

The multiset resulting from the addition of the sets.

copy()

Return a shallow copy of the multiset.

difference(*others)

Return a new multiset with all elements from the others removed.

>>> ms = Multiset('aab')
>>> sorted(ms.difference('bc'))
['a', 'a']

You can also use the - operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aabbbc')
>>> sorted(ms - Multiset('abd'))
['a', 'b', 'b', 'c']

For a variant of the operation which modifies the multiset in place see difference_update().

Parameters

others – The other sets to remove from the multiset. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

Returns

The resulting difference multiset.

distinct_elements()

classmethod from_elements(elements, multiplicity)

Create a new multiset with the given elements and each multiplicity set to multiplicity.

Uses dict.fromkeys() internally.

Parameters

• elements – The element for the new multiset.

• multiplicity – The multiplicity for all elements.

Returns

The new multiset.

get(element, default)

Return the multiplicity for element if it is in the multiset, else default.

Makes the default argument of the original dict.get() non-optional.

Parameters

• element – The element of which to get the multiplicity.

• default – The default value to return if the element if not in the multiset.

Returns

The multiplicity for element if it is in the multiset, else default.

intersection(*others)

Return a new multiset with elements common to the multiset and all others.

>>> ms = Multiset('aab')
>>> sorted(ms.intersection('abc'))
['a', 'b']

You can also use the & operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aab')
>>> sorted(ms & Multiset('aaac'))
['a', 'a']

For a variant of the operation which modifies the multiset in place see intersection_update().

Parameters

others – The other sets intersect with the multiset. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

Returns

The multiset resulting from the intersection of the sets.

isdisjoint(other)

Return True if the set has no elements in common with other.

Sets are disjoint iff their intersection is the empty set.

>>> ms = Multiset('aab')
>>> ms.isdisjoint('bc')
False
>>> ms.isdisjoint(Multiset('ccd'))
True

Parameters

other – The other set to check disjointedness. Can also be an Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

issubset(other)

Return True iff this set is a subset of the other.

>>> Multiset('ab').issubset('aabc')
True
>>> Multiset('aabb').issubset(Multiset('aabc'))
False

You can also use the <= operator for this comparison:

>>> Multiset('ab') <= Multiset('ab')
True

When using the < operator for comparison, the sets are checked to be unequal in addition:

>>> Multiset('ab') < Multiset('ab')
False

Parameters

other – The potential superset of the multiset to be checked.

Returns

True iff this set is a subset of the other.

issuperset(other)

Return True iff this multiset is a superset of the other.

>>> Multiset('aabc').issuperset('ab')
True
>>> Multiset('aabc').issuperset(Multiset('abcc'))
False

You can also use the >= operator for this comparison:

>>> Multiset('ab') >= Multiset('ab')
True

When using the > operator for comparison, the sets are checked to be unequal in addition:

>>> Multiset('ab') > Multiset('ab')
False

Parameters

other – The potential subset of the multiset to be checked.

Returns

True iff this set is a subset of the other.

items()

multiplicities()

symmetric_difference(other)

Return a new set with elements in either the set or other but not both.

>>> ms = Multiset('aab')
>>> sorted(ms.symmetric_difference('abc'))
['a', 'c']

You can also use the ^ operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aab')
>>> sorted(ms ^ Multiset('aaac'))
['a', 'b', 'c']

For a variant of the operation which modifies the multiset in place see symmetric_difference_update().

Parameters

other – The other set to take the symmetric difference with. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

Returns

The resulting symmetric difference multiset.

times(factor)

Return a new set with each element’s multiplicity multiplied with the given scalar factor.

>>> ms = Multiset('aab')
>>> sorted(ms.times(2))
['a', 'a', 'a', 'a', 'b', 'b']

You can also use the * operator for the same effect:

>>> sorted(ms * 3)
['a', 'a', 'a', 'a', 'a', 'a', 'b', 'b', 'b']

For a variant of the operation which modifies the multiset in place see times_update().

Parameters

factor – The factor to multiply each multiplicity with.

union(*others)

Return a new multiset with all elements from the multiset and the others with maximal multiplicities.

>>> ms = Multiset('aab')
>>> sorted(ms.union('bc'))
['a', 'a', 'b', 'c']

You can also use the | operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aab')
>>> sorted(ms | Multiset('aaa'))
['a', 'a', 'a', 'b']

For a variant of the operation which modifies the multiset in place see union_update().

Parameters

*others – The other sets to union the multiset with. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

Returns

The multiset resulting from the union.

values()

class multiset.FrozenMultiset(iterable=None)

Bases: multiset.BaseMultiset

The frozen multiset variant that is immutable and hashable.

class multiset.Multiset(iterable=None)

Bases: multiset.BaseMultiset

The mutable multiset variant.

add(element, multiplicity=1)

Adds an element to the multiset.

>>> ms = Multiset()
>>> ms.add('a')
>>> sorted(ms)
['a']

An optional multiplicity can be specified to define how many of the element are added:

>>> ms.add('b', 2)
>>> sorted(ms)
['a', 'b', 'b']

This extends the MutableSet.add() signature to allow specifying the multiplicity.

Parameters

• element – The element to add to the multiset.

• multiplicity – The multiplicity i.e. count of elements to add.

clear()

Empty the multiset.

difference_update(*others)

Remove all elements contained the others from this multiset.

>>> ms = Multiset('aab')
>>> ms.difference_update('abc')
>>> sorted(ms)
['a']

You can also use the -= operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aabbbc')
>>> ms -= Multiset('abd')
>>> sorted(ms)
['a', 'b', 'b', 'c']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see difference().

Parameters

others – The other sets to remove from this multiset. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

discard(element, multiplicity=None)

Removes the element from the multiset.

If multiplicity is None, all occurrences of the element are removed:

>>> ms = Multiset('aab')
>>> ms.discard('a')
2
>>> sorted(ms)
['b']

Otherwise, the multiplicity is subtracted from the one in the multiset and the old multiplicity is removed:

>>> ms = Multiset('aab')
>>> ms.discard('a', 1)
2
>>> sorted(ms)
['a', 'b']

In contrast to remove(), this does not raise an error if the element is not in the multiset:

>>> ms = Multiset('a')
>>> ms.discard('b')
0
>>> sorted(ms)
['a']

It is also not an error to remove more elements than are in the set:

>>> ms.remove('a', 2)
1
>>> sorted(ms)
[]

Parameters

• element – The element to remove from the multiset.

• multiplicity – An optional multiplicity i.e. count of elements to remove.

Returns

The multiplicity of the element in the multiset before the removal.

intersection_update(*others)

Update the multiset, keeping only elements found in it and all others.

>>> ms = Multiset('aab')
>>> ms.intersection_update('bc')
>>> sorted(ms)
['b']

You can also use the &= operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aabc')
>>> ms &= Multiset('abbd')
>>> sorted(ms)
['a', 'b']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see intersection().

Parameters

others – The other sets to intersect this multiset with. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

pop(element, default)

If element is in the multiset, remove it and return its multiplicity, else return default.

Makes the default argument of the original dict.pop() non-optional.

Parameters

• element – The element which is removed.

• default – The default value to return if the element if not in the multiset.

Returns

The multiplicity for element if it is in the multiset, else default.

remove(element, multiplicity=None)

Removes an element from the multiset.

If no multiplicity is specified, the element is completely removed from the multiset:

>>> ms = Multiset('aabbbc')
>>> ms.remove('a')
2
>>> sorted(ms)
['b', 'b', 'b', 'c']

If the multiplicity is given, it is subtracted from the element’s multiplicity in the multiset:

>>> ms.remove('b', 2)
3
>>> sorted(ms)
['b', 'c']

It is not an error to remove more elements than are in the set:

>>> ms.remove('b', 2)
1
>>> sorted(ms)
['c']

This extends the MutableSet.remove() signature to allow specifying the multiplicity.

Parameters

• element – The element to remove from the multiset.

• multiplicity – An optional multiplicity i.e. count of elements to remove.

Returns

The multiplicity of the element in the multiset before the removal.

Raises

KeyError – if the element is not contained in the set. Use discard() if you do not want an exception to be raised.

setdefault(element, default)

If element is in the multiset, return its multiplicity. Else add it with a multiplicity of default and return default.

Makes the default argument of the original dict.setdefault() non-optional.

Parameters

• element – The element which is added if not already present.

• default – The default multiplicity to add the element with if not in the multiset.

Returns

The multiplicity for element if it is in the multiset, else default.

symmetric_difference_update(other)

Update the multiset to contain only elements in either this multiset or the other but not both.

>>> ms = Multiset('aab')
>>> ms.symmetric_difference_update('abc')
>>> sorted(ms)
['a', 'c']

You can also use the ^= operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aabbbc')
>>> ms ^= Multiset('abd')
>>> sorted(ms)
['a', 'b', 'b', 'c', 'd']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see symmetric_difference().

Parameters

other – The other set to take the symmetric difference with. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

times_update(factor)

Update each this multiset by multiplying each element’s multiplicity with the given scalar factor.

>>> ms = Multiset('aab')
>>> ms.times_update(2)
>>> sorted(ms)
['a', 'a', 'a', 'a', 'b', 'b']

You can also use the *= operator for the same effect:

>>> ms = Multiset('ac')
>>> ms *= 3
>>> sorted(ms)
['a', 'a', 'a', 'c', 'c', 'c']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see times().

Parameters

factor – The factor to multiply each multiplicity with.

union_update(*others)

Update the multiset, adding elements from all others using the maximum multiplicity.

>>> ms = Multiset('aab')
>>> ms.union_update('bc')
>>> sorted(ms)
['a', 'a', 'b', 'c']

You can also use the |= operator for the same effect. However, the operator version will only accept a set as other operator, not any iterable, to avoid errors.

>>> ms = Multiset('aab')
>>> ms |= Multiset('bccd')
>>> sorted(ms)
['a', 'a', 'b', 'c', 'c', 'd']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see union().

Parameters

others – The other sets to union this multiset with. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

update(*others, **kwargs)

Like dict.update() but add multiplicities instead of replacing them.

>>> ms = Multiset('aab')
>>> ms.update('abc')
>>> sorted(ms)
['a', 'a', 'a', 'b', 'b', 'c']

Note that the operator += is equivalent to update(), except that the operator will only accept sets to avoid accidental errors.

>>> ms += Multiset('bc')
>>> sorted(ms)
['a', 'a', 'a', 'b', 'b', 'b', 'c', 'c']

For a variant of the operation which does not modify the multiset, but returns a new multiset instead see combine().

Any keyword arguments are also added to the multiset:

>>> ms = Multiset('ab')
>>> ms.update(a=1, e=2)
>>> sorted(ms)
['a', 'a', 'b', 'e', 'e']

Parameters

• others – The other sets to add to this multiset. Can also be any Iterable[~T] or Mapping[~T, int] which are then converted to Multiset[~T].

• kwargs – Additional pairs of values and multiplicities to be added to multiset.