6

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!

3
  • What have you tried? Can you show us a minimum working set of code that demonstrates your question and what you are trying to accomplish?
    – Engineero
    Jun 15, 2016 at 21:40
  • 3
    Could you provide an example of what you are trying to do? This sounds a bit counter intuitive of using sets since part of an object being unique in a set is that is has a unique __hash__. Jun 15, 2016 at 21:41
  • Even mathematically this doesn't make sense. A set is defined as having no duplicates. Essentially all elements in a set is not equal to each other, therefore to be in a set, an equality comparison between all elements must already exist. If you could explain what you're trying to accomplish more, it might make your motive in these intersections clearer! Jun 15, 2016 at 22:19

2 Answers 2

9

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]
1
  • Thanks for this detailed and very useful answer!!
    – PraMiD
    Jun 20, 2016 at 21:13
1

One approach would be to write your own subclass of Set and implement custom comparisons that way. Then, you'd just have to create a new instance of the custom "keyed set" per "equality" that you want to get an intersection of your elements using.

For instance: http://code.activestate.com/recipes/576932-sets-with-a-custom-equalityuniqueness-function/

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.