ActiveState Code

Recipe 499354: Equivalence partition

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 
 1
 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

Discussion

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.

Comments

  1. 1. At 4:51 p.m. on 6 jan 2007, Steven Bethard said:

    for-loop's else clause. The code

    found = False
for c in classes:
    if relation(iter(c).next(), o):
        c.add(o)
        partitions[o] = c
        found = True
        break
if not found:
    classes.append(set([o]))
    partitions[o] = classes[-1]

    is normally written using the for-loop's else clause:

    for c in classes:
    if relation(iter(c).next(), o):
        c.add(o)
        partitions[o] = c
        break
else:
    classes.append(set([o]))
    partitions[o] = classes[-1]
  2. 2. At 2:20 a.m. on 9 jan 2007, John Reid (the author) said:

    Thanks. I had never seen that construct before, I'm still a bit new to python.

  3. 3. At 5:08 p.m. on 16 feb 2007, D Torpey said:

    Seems like a lot of code to do very little. Compare to:

    def partition(domain, relation):
    known = set()
    classes = {}
    for x in domain:
        for representative, values in classes.items():
            if relation(x, representative):
                values.add(x)
                break
        else:
            classes[x] = set([x])
    return classes.values()

print partition(xrange(-3, 5), lambda x,y: (x-y) % 4 == 0)
  4. 4. At 7:04 a.m. on 13 apr 2007, John Reid (the author) said:

    More code to do more? If you look at the code you'll see most of the extra lines are extra functionality or comments.

Sign in to comment