Source code for libutilitaspy.data_structures.partitions
'''
Provides utilities for creating set partitions.
@author: eposse
'''
class EqWrap(object):
def __init__(self, obj, eq):
self.obj = obj
self.eq = eq
def __hash__(self):
return hash(self.obj.__class__)
def __eq__(self, other):
return self.eq(self.obj, other.obj)
[docs]def create_partition(l):
"""
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)
"""
partition_table = {}
for item in l:
try:
partition_table[item].append(item)
except KeyError:
partition_table[item] = [item]
return partition_table
[docs]def create_partition_eq(l, eq):
"""
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)
"""
new_l = [EqWrap(obj, eq) for obj in l]
return create_partition(new_l)
class Partition(object):
def __init__(self, lst, eq=None):
self.__create_partition_tables(lst, eq)
def __create_partition_tables(self, l, eq=None):
if eq is not None:
l = [EqWrap(obj, eq) for obj in l]
self.partition_table = {}
self.partition_index = {}
for item in l:
try:
self.partition_table = [item].append(item)
self.partition_index[item] = item
except KeyError:
self.partition_table[item] = [item]
self.partition_index[item] = item
def canonical(self, element):
"""Returns the part of the partition which contains the element."""
return self.partition_table[element]
def representative(self, part):
"""Returns an element (any) in the given part."""
pass