Is there a standard way to partition an interable into equivalence classes given a relation in python?

Question

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

Is there a standard way to do this in python? Better yet, is there a module designed to deal with equivalence relations?

Seigler

Have you already tried to write some code yourself? Have you googled Python equivalence classes ? – Loggins

itertools.groupby is useful if you can compute a canonical element of each equivalence class from an arbitrary value. – Magalimagallanes

@Magalimagallanes I think that that's what's interesting in the question, though - the specification by an equivalence class. BTW, as you know, groupby requires them to be sorted - another difficulty with the current formulation. – Graduation

Defining such a function is the key, of course, but the same one can be used with the sorted function to get the order required. – Magalimagallanes

@Loggins I did write something myself. The reason I'm asking here is that I want something that runs as efficiently as possible. I'm writing code for my research (I'm a mathematician, not a computer scientist). – Seigler

@Loggins Also thanks for pointing me to google! – Seigler

@Magalimagallanes But if there is such a canonical key function, then sorting is an overkill in terms of complexity, no? – Graduation

Answer 1

The following function takes an iterable 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]]

Graduation

Answer 2

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

It seems to do what you want. Here's the adapted version I made in case 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. 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(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. 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.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()

Outfight

+1 for adapting the whole recipe, with the tests and everything. maybe you could add a link to your post to the AS recipe ? – Candice

Aw shucks, adapting the code probably took less effort than the other people here put into their answers. A couple of iteritems() -> items(), some tweaks to print...But yeah, linked. – Outfight

Answer 3

I'm not aware of any python library dealing with 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]]

Vicariate

Answer 4

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 a 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, this obviously doesn't work if my_relation returns a boolean. I'd say come up with some abstract way to represent each isomorphism, although I suspect that's the goal of trying to do this in the first place.

Quindecennial

I don't see the connection to the question. Your my_relation is actually a key function, not a binary function at all. – Graduation

The key function is an equivalence kernel for the relation. – Magalimagallanes

The best answer ! Made me delete mine, this is much better thought out. – Candice

@Candice I agree this is a good answer... but it only works if I already have the key function. In general, finding the key function is equivalent to solving my original problem. – Seigler

Ah yes this is true. I undeleted my answer just in case. It's very similar to Tagc's anyway. – Candice

@BrianFitzpatrick can you point me to an example of a binary relation that defines an equivalence class which does not have an evident key function? – Quindecennial

Well, mine is the collection of sub-posets of a given poset where the relation is given by poset-isomorphisms. – Seigler

Well, that was an interesting Wikipedia article. If that's the case you can use your relation function here and add and inner loop making this O(n^2) – Quindecennial

@Quindecennial Your code here is still useful in my example. Two elements of the same isomorphism class necessarily have the same rank. Running your code first on the rank function would simplify the process considerably (I think). – Seigler

Answer 5

Would 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 it with :

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

Which returned :

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

EDIT: If you want this to run as fast as possible, you may :

• wrap it in a Cython module (removing the defaultdict, there aren't much things to change)
• want to try running it with PyPy
• find a dedicated module (wasn't able to find any)

Candice

Could you expand on how one might wrap this in a cython module? – Seigler

Well, adapting this code to Cython wouldn't be too hard, as other than the defaultdict it does not use anything not available as Cython types. You'd have to rewrite this as .pyx file, declare variables using cdef, and then compile it to a Python module that you can import in a regular Python application. – Candice

Answer 6

The NetworkX library seems to have this feature built in. Maybe you can use it.

Lakenyalaker