Provides utilities for creating set partitions.
@author: eposse
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’).
Like create_partition, but the partition is created with respect to the equivalence relation eq, rather than the __eq__ method of objects in l.