Python 与自定义相等的交集

Question

我想构建两个 python 集合的交集，但我需要自定义等式来执行此操作。有没有办法在做交集的时候直接指定"equaliy"？例如由于 lambda 表达式?

我知道可以通过覆盖 eq，但我必须在同一个类上与不同的 "equalities".[=11 做几个交集=]

谢谢！

Answer 1

一种方法是编写您自己的 Set 子类并以这种方式实现自定义比较。然后，您只需要根据 "equality" 创建自定义 "keyed set" 的新实例，您希望使用它来获取元素的交集。

例如：http://code.activestate.com/recipes/576932-sets-with-a-custom-equalityuniqueness-function/

Answer 2

前言

通过使用正确的术语，您正在尝试做的事情具有完美的数学意义。你说的"equalities"实际上是equivalence relations。基本上，equicalenve 关系描述了一个必须满足的条件，以便将集合的两个元素标识为 "equivalent"。

等价关系将一个集合不相交地分解为所谓的等价 classes。每个等价 class 是一个子集，它包含原始集合中关于等价关系成对等价的所有元素。

等式本身就是等价关系的一个特例。等式关系的每个等价 class 仅包含一个元素，因为集合中的每个元素仅等于其自身。

远足： 当谈到面向对象语言中的对象相等时，这是一个混淆的来源。在数学中，一个对象（即集合的成员）只存在一次（它只等于它自己）。然而，在面向对象编程中，存在同一性和相等性的区别。可以有不同身份的对象（Python：a is b 计算结果为假）相等（a == b 计算结果为真），例如 float 2.0和 int 2。这意味着，Python 的 __eq__ 函数在所有 Python 对象的集合上实现了一个默认的等价关系，称为 "equality"。 游览结束

关于任何等价 class 的一个更重要的事情是，它可以由单个任意成员（称为 "representative"）表示。这意味着您只需要检查与等价 class 的一个已知代表的关系，以确定一个元素是否属于该等价 class。这将在下面的代码中被利用。

问题的答案

根据您的问题，我们有以下设置。我们有两个集合 A 和 B，它们实际上是更大集合 M 的子集。对于 M 有许多不同的等价关系，对于每一个，我们需要 "intersect" A 和 B "with respect to the equivalence relation" 以某种方式。

唯一有意义的方法是用等价的 class 替换 A 和 B 的成员，并检查哪些等价的 class 是出现在两个投影中。

这比听起来容易：关于一个等价关系的交集方法：

将 A（和 B 的元素分别分组），使每个组都包含成对的等效元素。（这些组类似于等价 classes）
对于 A 的每个 G 组，检查是否存在 B 的组 H 使得 G 和 [=31] 的元素=] 是等价的。如果是，则G和H属于同一个等价class，即等价class是交集

请注意，所需的输出实际上取决于您的用例。你可以例如使用匹配 Gs 和 Hs 的所有并集的列表（这是下面实现的）。或者，如果您只对交集中每个等价 class 的任意元素感兴趣，则可以选择 G（或 H）的第一个成员。（这在 __main__ 部分中显示为 [c[0] for c in intersection]。）

下面的代码示例使用适用于任何对象和任何等价关系的列表（不是集合或代表）实现了如上所述的朴素交集。 Intersector class 接受一个带有两个参数的函数，如果两个参数相等，则 returns 为真。

我假设您可以轻松优化您的用例以节省循环和比较。

重要说明：当然你需要验证你的"equalities"是真正的等价关系（自反性，对称性，传递性，见上面的wiki link ).

代码：

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 与自定义相等的交集

Python intersection with custom equality

python

lambda

intersection