具有自定义相等性的Python相交 [英] Python intersection with custom equality

问题描述

我想建立两个python集的交集，但是我需要有一个自定义的相等性来做到这一点. 进行交点时，是否可以直接指定相等"?例如由于lambda表达式?

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?

我知道可以通过重写 eq 来解决问题，但是我必须在具有不同等式"的同一个类上进行多个交集.

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

谢谢！

推荐答案

前言

通过使用正确的术语，您尝试做的事情具有完美的数学意义.您所指的平等"实际上是等效关系.基本上，等距关系描述了将集合的两个元素标识为等效"所必须满足的条件.

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.

游览:当谈到面向对象的语言中的对象平等时，这会引起混乱.在数学中，对象(即集合的成员)仅存在一次(它仅等于自身).但是，在面向对象的编程中，存在身份和相等性的区别.可能存在具有相同身份(Python:a is b评估为false)(a == b评估为true)的对象，例如float 2.0和int 2.这意味着，Python的__eq__函数在所有Python对象的集合上实现了默认的等价关系，这称为相等". 游览结束

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.

问题答案

根据您的问题，我们有以下设置.我们有两组A和B，它们实际上是较大组M的子集.对于M，存在许多不同的等价关系，而对于每种关系，我们都需要以某种方式相交" A和B关于等价关系".

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.

唯一有意义的方法是用等价类替换A和B的成员，并检查两个投影中确实发生了哪些等价类.

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. 对A的元素(和分别为B)进行分组，以使每个组由成对的等效元素组成. (这些组类似于等效类)
2. 对于A的每个组G，请检查是否存在B的组H，以使G和H的元素相等.如果是，则G和H属于相同的等价类，即等价类是交集的成员.

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.

请注意，所需的输出实际上取决于您的用例.您可以例如使用匹配的G和H的所有并集的列表(这是下面要强调的内容).或者，如果您只对交点中每个等价类的任意元素感兴趣，则可以选择G(或H)的第一个成员. (这在__main__部分显示为[c[0] for c in 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].)

下面的代码示例使用列表(不是集合或代表)实现了如上所述的幼稚相交，该列表适用于任何对象和任何等价关系. Intersector类采用具有两个参数的函数，如果两个参数相等，则该函数返回true.

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.

重要提示:当然，您需要验证您的等式"是非对等关系(反射性，对称性，传递性，请参见上面的Wiki链接).

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

代码:

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)

输出:

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]

这篇关于具有自定义相等性的Python相交的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！