Python中的自定义相等性交集

Question

我想构建两个Python集合的交集，但是我需要有自定义相等性的方法来实现这一点。在执行交集操作时，是否有一种直接指定“相等性”的方法？例如使用lambda表达式。

我知道可以通过重写< strong>eq的方式来完成，但我必须在具有不同“相等性”的相同类上执行多个交集。

谢谢！

- PraMiD

---

你尝试过什么？你能展示一个最小的工作代码集，演示你的问题以及你想要实现的内容吗？ - Engineero

请举个例子说明你试图做什么？使用集合似乎有些违反直觉，因为对象在集合中的唯一性取决于其具有唯一的__hash__。 - Tadhg McDonald-Jensen

即使从数学上讲，这也是没有意义的。集合被定义为不含重复元素。实际上，集合中的所有元素都不相等，因此要成为集合中的一员，所有元素之间必须已经存在相等比较。如果您能更详细地解释您想要实现什么，可能会更清楚您在这些交集中的动机！ - define cindy const

Answer 1

前言

如果使用正确的术语，您正在尝试做出完全符合数学意义的事情。您所指的“等式”实际上是等价关系。基本上，等价关系描述了必须满足的条件，以便将集合中的两个元素标识为“等价的”。

等价关系将一个集合分解成所谓的等价类。每个等价类都是一个子集，其中包含原始集合中所有在等价关系方面成对等价的元素。

相等本身是等价关系的一种特殊情况。等式关系的每个等价类只包含一个元素，因为集合中的每个元素只等于它本身。

插曲：这是在面向对象语言中讨论对象相等性时产生困惑的源头。在数学中，对象（即集合的成员）仅存在一次（它只等于它本身）。然而，在面向对象编程中，有身份和相等之分。可以具有不同身份的对象（Python：a is b计算结果为false），它们是相等的（a == b计算结果为true），例如float 2.0和int 2。这意味着，Python的__eq__函数在所有Python对象的集合上实现了一个名为“相等”的默认等价关系。 插曲结束

关于任何等价类的另一个重要事项是，它可以由单个任意成员（称为“代表”）表示。这意味着，您只需要针对等价类的一个已知代表检查关系，即可决定元素是否属于该等价类。下面的代码将利用这一点。

回答问题

与您的问题相对应，我们有以下设置。我们有两个集合A和B，它们实际上是更大集合M的子集。对于M，有许多不同的等价关系，对于每个等价关系，我们都需要以某种方式“根据等价关系与A和B进行“交集”。

唯一有意义的方法是通过它们的等价类替换A和B的成员，并检查哪些等价类同时出现在两个投影中。

这比听起来要容易：根据一个等价关系进行交集的配方：

1. 将A（和B）的元素分组，使得每个组都由成对等价的元素组成。（这些组类似于等价类）
2. 对于A的每个组G，检查是否存在B的组H，使得G和H的元素是等价的。如果是，则G和H属于同一等价类，即该等价类是交集的成员。

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

下面的代码示例使用列表（而不是集合或代表）实现了上述简单交集，适用于任何对象和任何等价关系。 Intersector类采用具有两个参数的函数，如果两个参数相等，则返回true。

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

重要提示：当然，您需要验证您的“相等性”是否是实际的等价关系（自反性，对称性，传递性，请参见上面的维基链接）。

代码：

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]

- code_onkel

---

非常感谢您提供这么详细和有用的答案！！ - PraMiD

Answer 2

一种方法是编写自己的Set子类，并以此实现自定义比较。然后，您只需创建一个新的自定义“键集”实例，每个“相等性”都希望使用它来获取元素的交集即可。

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

- Jomel Imperio