libutilitaspy.data_structures.partitions

Provides utilities for creating set partitions.

@author: eposse

libutilitaspy.data_structures.partitions.create_partition(l)[source]

Given an iterable object l of comparable/hashable objects, return a partition table, namely the quotient of the set of elements in the list with respect to the equivalence relation given by the equality operation between the objects (as implemented by the __eq__ method).

This partition is a dictionary p, whose keys are elements of the list, and for a given element x from l, the corresponding value p[x] is the list of all elements y in l such that x == y.

The partition is computed as follows:

For every item x in the list l, check if there is already an entry p[x]. More precisely, check if there is already a key y in p such that x == y. If so, add x to the list p[y]. If not, create a new entry p[x] and set it to be the list [x].

The result is computing by taking advantage of the semantics of dictionaries in Python: the __getitem__ operation invoked when accessing the entry p[x], first computes the hash value of x to get a quick access to the underlying table, and then, if there is a key x’ in p with that hash value, Python checks to see if id(x) is id(x’). If so, they are the same object. If not, Python tries to compare with equality: x == x’. If they are equivalent, they are assumed to be the same key, because all hashable objects x and x’ which compare equal, x == x’, must have hash(x) == hash(x’).

Parameters:
l: ‘a list
Returns:
(‘a, ‘a list) dict
A dictionary mapping elements of l to their equivalence class
Preconditions:
All elements in l must be hashable and comparable:
all(hashable(x) for x in l)
libutilitaspy.data_structures.partitions.create_partition_eq(l, eq)[source]

Like create_partition, but the partition is created with respect to the equivalence relation eq, rather than the __eq__ method of objects in l.

Parameters:
l: ‘a list eq: ‘a * ‘a -> bool
Returns:
(‘a, ‘a list) dict
A dictionary mapping elements of l to their equivalence class
Preconditions:
eq is an equivalence relation (more precisely, the characteristic function of an equivalence relation)

Previous topic

libutilitaspy.data_structures.priority_queues

Next topic

categories package

This Page