Partitions a set of objects into classes according to some supplied equivalence relation. Useful when you know when objects are equivalent but cannot categorise them into groups easily.
Python, 70 lines
Download
Copy to clipboard1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 | def equivalence_partition( iterable, relation ):
"""Partitions a set of objects into equivalence classes
Args:
iterable: collection of objects to be partitioned
relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
if and only if o1 and o2 are equivalent
Returns: classes, partitions
classes: A sequence of sets. Each one is an equivalence class
partitions: A dictionary mapping objects to equivalence classes
"""
classes = []
partitions = { }
for o in iterable: # for each object
# find the class it is in
found = False
for c in classes:
if relation( iter(c).next(), o ): # is it equivalent to this class?
c.add( o )
partitions[o] = c
found = True
break
if not found: # it is in a new class
classes.append( set( [ o ] ) )
partitions[o] = classes[-1]
return classes, partitions
def equivalence_enumeration( iterable, relation ):
"""Partitions a set of objects into equivalence classes
Same as equivalence_partition() but also numbers the classes.
Args:
iterable: collection of objects to be partitioned
relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
if and only if o1 and o2 are equivalent
Returns: classes, partitions, ids
classes: A sequence of sets. Each one is an equivalence class
partitions: A dictionary mapping objects to equivalence classes
ids: A dictionary mapping objects to the indices of their equivalence classes
"""
classes, partitions = equivalence_partition( iterable, relation )
ids = { }
for i, c in enumerate( classes ):
for o in c:
ids[o] = i
return classes, partitions, ids
def check_equivalence_partition( classes, partitions, relation ):
"""Checks that a partition is consistent under the relationship"""
for o, c in partitions.iteritems():
for _c in classes:
assert (o in _c) ^ (not _c is c)
for c1 in classes:
for o1 in c1:
for c2 in classes:
for o2 in c2:
assert (c1 is c2) ^ (not relation( o1, o2 ))
def test_equivalence_partition():
relation = lambda x,y: (x-y) % 4 == 0
classes, partitions = equivalence_partition(
xrange( -3, 5 ),
relation
)
check_equivalence_partition( classes, partitions, relation )
for c in classes: print c
for o, c in partitions.iteritems(): print o, ':', c
|
This is similar to David Dai's recipe (http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/498223). His recipe is for the case when you already have a categorising function. In my use case you have a function that determines if two objects are equivalent.
test_equivalence_partition() produces the following output: set([1, -3]) set([2, -2]) set([3, -1]) set([0, 4]) 0 : set([0, 4]) 1 : set([1, -3]) 2 : set([2, -2]) 3 : set([3, -1]) 4 : set([0, 4]) -2 : set([2, -2]) -3 : set([1, -3]) -1 : set([3, -1])
Hope someone finds this useful...
John.
Tags: algorithms
for-loop's else clause. The code
is normally written using the for-loop's else clause:
Thanks. I had never seen that construct before, I'm still a bit new to python.
Seems like a lot of code to do very little. Compare to:
More code to do more? If you look at the code you'll see most of the extra lines are extra functionality or comments.
Here's a version of John Reid's recipe that's been adapted to Python 3.