Python intersection with custom equality

Question

I want to build the intersection of two python sets, but i need to have a custom equality to do this. Is there a way to specify "equaliy" directly when doing the intersection? For example due to a lambda-expressions?

I know there is way by overriding eq, but i have to do several intersections on the same classes with different "equalities".

Thanks!

Answer 1

Preface

What you are trying to do makes perfect mathematical sense by using the right terms. The "equalities" you are referring to are actually equivalence relations. Basically an equicalenve relation describes a condition that must be met in order to identify two elements of a set as "equivalent".

An equivalence relation disjointly decomposes a set into so called equivalence classes. Each equivalence class is a subset that contains all elements of the original set which are pairwise equivalent with respect to the equivalence relation.

Equality itself is a special case of an equivalence relation. Each equivalance class of the equality relation contains only one element since each element of a set only equals itself.

Excursion: This is a source of confusion when speaking of object equality in object oriented languages. In Mathematics, an object (i.e. the member of a set) exists only once (it only equals itself). In object oriented programming however, there is the distinction of identity and equality. There can be objects of different identity (Python: a is b evaluates to false) that are equal (a == b evaluates to true), for example the float 2.0 and the int 2. That means, that Python's __eq__ functions implements a default equivalence relation on the set of all Python objects which is called "equality". End of Excursion

One more important thing about any equivalence class is, that it can be represented by a single arbitrary member (called a "representative"). This implies that you only need to check the relation against one known representative of an equivalence class to decide if an element belongs to that equivalence class. This will be exploited in the code below.

Answer to the Question

Corresponding to your question we have the following setup. We have two sets A and B which are actually subsets of a larger set M. For M there are many different equivalence relations and for each of those, we need to "intersect" A and B "with respect to the equivalence relation" somehow.

The only way this makes sense, is to replace the members of A and B by their equivalence classes and to check which equivanlence classes do occur in both projections.

This is easier than it sounds: Recipe for intersection with respect to one equivalence relation:

1. Group the elements of A (and B respectively) such that each group consists of pairwise equivalent elements. (These groups resemble the equivalence classes)
2. For each group G of A, check if there is a group H of B such that elements of G and H are equivalent. If yes, G and H belong to the same equivalence class, i.e. that equivalence class is a member of the intersection.

Note that the wanted output actually depends on your use case. You could e.g. use the list of all unions of matching Gs and Hs (this is what is impemented below). Alternatively, you could choose the first member of G (or H) if you are only interested in an arbitrary element of each equivalence class in the intersection. (This is demonstrated in the __main__ section as [c[0] for c in intersection].)

The code sample below implements a naive intersection as described above using lists (not sets or representatives) which works with any object and any equivalence relation. The Intersector class takes a function with two arguments that returns true if the two arguments are equivalent.

I assume that you can make easy optimisations for your use case to save loops and comparisons.

Important note: Of course you need to verify that your "equalities" are acutal equivalence relations (Reflexivity, Symmetry, Transitivity, see wiki link above).

Code:

from __future__ import print_function

class Intersector(object):
    def __init__(self, relation):
        self.relation = relation

    def intersect(self, a, b):
        a_classes = self.get_equivalence_classes(a)
        print('Groups of A:', a_classes)
        b_classes = self.get_equivalence_classes(b)
        print('Groups of B:', b_classes)
        return self.intersect_classes(a_classes, b_classes)

    def get_equivalence_classes(self, elements):
        eq_classes = []
        for element in elements:
            match = False
            for eq_class in eq_classes:
                if self.relation(element, eq_class[0]):
                    eq_class.append(element)
                    match = True
                    break

            if not match:
                eq_classes.append([element])
        return eq_classes

    def intersect_classes(self, a, b):
        def search_in_B(g):
            for h in b:
                if self.relation(g[0], h[0]):
                    return h
        result = []
        for g in a:
            h = search_in_B(g)
            if h is not None:
                result.append(g+h)
        print('Intersection:', result)
        return result


if __name__ == '__main__':
    A = set([4, 2, 1, 7, 0])
    B = set([1, 13, 23, 12, 62, 101, 991, 1011, 1337, 66, 666])

    print('A:', A)
    print('B:', B)
    print(79*'-')

    print('Intersection with respect to the relation:')
    print('a and b have the same remainder divided by 5')
    intersection = Intersector(lambda x, y : x % 5 == y % 5).intersect(A, B)
    reduced = [c[0] for c in intersection]
    print('Intersection reduced to representatives:', reduced)

    print(79*'-')

    print('Intersection with respect to the relation:')
    print('a and b have the same remainder divided by 7')
    intersection = Intersector(lambda x, y : x % 7 == y % 7).intersect(A, B)
    reduced = [c[0] for c in intersection]
    print('Intersection reduced to representatives:', reduced)

Output:

A: set([0, 1, 2, 4, 7])
B: set([1, 66, 101, 12, 13, 1011, 23, 1337, 666, 62, 991])
-------------------------------------------------------------------------------
Intersection with respect to the relation:
a and b have the same remainder divided by 5
Groups of A: [[0], [1], [2, 7], [4]]
Groups of B: [[1, 66, 101, 1011, 666, 991], [12, 1337, 62], [13, 23]]
Intersection: [[1, 1, 66, 101, 1011, 666, 991], [2, 7, 12, 1337, 62]]
Intersection reduced to representatives: [1, 2]
-------------------------------------------------------------------------------
Intersection with respect to the relation:
a and b have the same remainder divided by 7
Groups of A: [[0, 7], [1], [2], [4]]
Groups of B: [[1, 666], [66, 101, 1011], [12], [13, 62], [23], [1337], [991]]
Intersection: [[0, 7, 1337], [1, 1, 666], [2, 23], [4, 991]]
Intersection reduced to representatives: [0, 1, 2, 4]