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