bags (Multisets)

bag is a multiset implementation for Python. Currently, bags have constant time inclusion testing but can only contain hashable elements due to the implementation.

There are two classes provided:

bag
A mutable (unhashable) bag.
frozenbag
An immutable (implements collections.abc.Hashable) version of a bag.

Both classes implement collections.abc.Sized, collections.abc.Iterable and collections.abc.Container. Both classes implement collections.abc.Collection starting in Python 3.6.

Set Operations

bag and frozenbag use python operators for multiset operations:

  • __add__ (a + b): The sum of two multisets
  • __sub__ (a - b): The difference between a and b
  • __and__ (a & b): The intersection of a and b
  • __or__ (a | b): The union of a and b
  • __xor__ (a ^ b): The symmetric difference between a and b

bag has the equivalent in-place operators defined.

Comparison Methods

Bags are comparable to Sets (including other bags). When comparing a bag to a Set, the Set is treated as a bag with all multiplicities equal to 1. The ordering comparison operators are implemented using multiset comparison.

>>> bag() == set()
True
>>> bag('a') == set('a')
True
>>> bag('ab') == set('a')
False
>>> bag('a') == set('ab')
False
>>> bag('aa') == set('a')
False
>>> bag('aa') == set('ab')
False
>>> bag('ac') == set('ab')
False
>>> bag('ac') <= set('ab')
False
>>> bag('ac') >= set('ab')
False
>>> bag('a') <= bag('a') < bag('aa')
True
>>> bag('aa') <= bag('a')
False

Compared to existing similar implementations

collections.Counter

Counters don’t really behave like Collections - Sized, Iterable, Containers

Adding and Removing

>>> c = Counter()
>>> c['a'] += 1
>>> c['a'] -= 1
>>> 'a' in c
True
>>> b = bag()
>>> b.add('a')
>>> 'a' in b
True
>>> b.remove('a')
>>> 'a' in b
False

len

>>> c = Counter()
>>> c['a'] += 1
>>> len(c)
1
>>> c['a'] -= 1
>>> len(c)
1
>>> c['a'] += 2
>>> len(c)
1
>>> len(Counter('aaabbc'))
3
>>> b = bag()
>>> b.add('a')
>>> len(b)
1
>>> b.remove('a')
>>> len(b)
0
>>> len(bag('aaabbc'))
6

Iterating

>>> for item in Counter('aaa'): print(item)
a
>>> for item in bag('aaa'): print(item)
a
a
a

Compared to Standard Types

bag vs. list

  • Inclusion testing is O(1)
  • Adding and removing elements is O(1)
  • Cannot add mutable elements
  • Elements aren’t ordered

bag vs. set

  • Can add multiple instances of equal elements

New Methods

num_unique_elements
Returns the number of unique elements in the bag. O(1)
unique_elements()
Returns a set of all the unique elements in the bag. O(1)
nlargest(n=None)
Returns the n most common elements and their counts from most common to least. If n is None then all elements are returned. O(n log n)
copy()
Returns a shallow copy of self. O(self.num_unique_elements())
isdisjoint(other: Iterable)
Tests if self is disjoint with any other Iterable. O(len(other))
is_subset(other: Set)
Tests if self is a subset of another Set.
is_superset(other: Set)
Tests if self is a superset of another Set.
from_mapping(map: Mapping)
Classmethod to create a bag from a Mapping that maps elements to counts.

The following are only for mutable bags (not frozenbags).

  • pop()
  • add(elem)
  • discard(elem)
  • remove(elem)
  • clear()

API

bag

class collections_extended.bag(iterable=None)[source]

bag is a mutable unhashable bag.

__init__(iterable=None)

Create a new bag.

If iterable isn’t given, is None or is empty then the bag starts empty. Otherwise each element from iterable will be added to the bag however many times it appears.

This runs in O(len(iterable))

frozenbag

class collections_extended.frozenbag(iterable=None)[source]

frozenbag is an immutable, hashable bag.

__init__(iterable=None)

Create a new bag.

If iterable isn’t given, is None or is empty then the bag starts empty. Otherwise each element from iterable will be added to the bag however many times it appears.

This runs in O(len(iterable))

Views

class collections_extended.CountsView(bag)[source]

A view for the unique items and their counts in a bag.

New in version 1.1.

class collections_extended.UniqueElementsView(bag)[source]

A view for the unique items and their counts in a bag.

New in version 1.1.