Is there a standard way to split Interable into equivalence classes given the relation in python?

Question

Say that I have a finite iterative X and an equivalence relation ~ on X We can define the function my_relation(x1, x2) , which returns True if x1~x2 and returns False otherwise. I want to write a function separating X into equivalence classes. That is, my_function(X, my_relation) should return a list of equivalence classes ~ .

Is there a standard way to do this in python? Even better, is there a module designed to address equivalence relations?

Answer 1

I found this Python recipe from John Reed. It was written in Python 2, and I adapted it to Python 3 to test it. The recipe includes a test to split the set of integers [-3,5) into equivalence classes based on the relationship lambda x, y: (x - y) % 4 == 0 .

You seem to be doing what you want. Here's an adapted version that I made if you want it in Python 3:

 def equivalence_partition(iterable, relation): """Partitions a set of objects into equivalence classes Args: iterable: collection of objects to be partitioned relation: equivalence relation. Ie 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(next(iter(c)), 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. Ie 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.items(): 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( range(-3, 5), relation ) check_equivalence_partition(classes, partitions, relation) for c in classes: print(c) for o, c in partitions.items(): print(o, ':', c) if __name__ == '__main__': test_equivalence_partition() 

Answer 2

 In [1]: def my_relation(x): ...: return x % 3 ...: In [2]: from collections import defaultdict In [3]: def partition(X, relation): ...: d = defaultdict(list) ...: for item in X: ...: d[my_relation(item)].append(item) ...: return d.values() ...: In [4]: X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] In [5]: partition(X, my_relation) Out[5]: [[3, 6, 9, 12], [1, 4, 7, 10], [2, 5, 8, 11]] 

For binary function:

 from collections import defaultdict from itertools import combinations def partition_binary(Y, relation): d = defaultdict(list) for (a, b) in combinations(Y): l = d[my_relation(a, b)] l.append(a) l.append(b) return d.values() 

You can do something like this:

 partition_binary(partition(X, rank), my_relation) 

Oh, that obviously doesn't work if my_relation returns a boolean. I would say, I came up with some abstract way to represent each isomorphism, although I suspect that the goal is to try to do this in the first place.

Answer 3

The following function takes an iterative a and an equivalence function equiv , and does what you ask:

 def partition(a, equiv): partitions = [] # Found partitions for e in a: # Loop over each element found = False # Note it is not yet part of a know partition for p in partitions: if equiv(e, p[0]): # Found a partition for it! p.append(e) found = True break if not found: # Make a new partition for it. partitions.append([e]) return partitions 

Example:

 def equiv_(lhs, rhs): return lhs % 3 == rhs % 3 a_ = range(10) >>> partition(a_, equiv_) [[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]] 

Answer 4

I don't know any python library related to equivalence relations.

Perhaps this snippet is useful:

 def rel(x1, x2): return x1 % 5 == x2 % 5 data = range(18) eqclasses = [] for x in data: for eqcls in eqclasses: if rel(x, eqcls[0]): # x is a member of this class eqcls.append(x) break else: # x belongs in a new class eqclasses.append([x]) eqclasses => [[0, 5, 10, 15], [1, 6, 11, 16], [2, 7, 12, 17], [3, 8, 13], [4, 9, 14]] 

Answer 5

Will this work?

 def equivalence_partition(iterable, relation): classes = defaultdict(set) for element in iterable: for sample, known in classes.items(): if relation(sample, element): known.add(element) break else: classes[element].add(element) return list(classes.values()) 

I tried:

 relation = lambda a, b: (a - b) % 2 equivalence_partition(range(4), relation) 

What came back:

 [{0, 1, 3}, {2}] 

EDIT: if you want it to be as fast as possible, you can:

• wrap it in a Cython module (removing defaultdict has nothing to change)
• I want to try running it with PyPy
• find the highlighted module (could not be found)