9

假设我有一个有限的可迭代X和等价关系~。X我们可以定义一个函数my_relation(x1, x2)，True如果x1~x2返回，False否则返回。我想编写一个划分X为等价类的函数。也就是说，my_function(X, my_relation)应该返回 的等价类列表~。

在python中有没有标准的方法来做到这一点？更好的是，是否有设计用于处理等价关系的模块？

4

5 回答 5

3

我找到了 John Reid 的这个 Python 食谱。它是用 Python 2 编写的，我将它改编为 Python 3 来测试它。该配方包括一个测试，用于[-3,5)根据关系将整数集划分为等价类lambda x, y: (x - y) % 4 == 0。

它似乎做你想做的事。这是我制作的改编版本，以防你在 Python 3 中需要它：

def equivalence_partition(iterable, relation):
    """Partitions a set of objects into equivalence classes

    Args:
        iterable: collection of objects to be partitioned
        relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
            if and only if o1 and o2 are equivalent

    Returns: classes, partitions
        classes: A sequence of sets. Each one is an equivalence class
        partitions: A dictionary mapping objects to equivalence classes
    """
    classes = []
    partitions = {}
    for o in iterable:  # for each object
        # find the class it is in
        found = False
        for c in classes:
            if relation(next(iter(c)), o):  # is it equivalent to this class?
                c.add(o)
                partitions[o] = c
                found = True
                break
        if not found:  # it is in a new class
            classes.append(set([o]))
            partitions[o] = classes[-1]
    return classes, partitions


def equivalence_enumeration(iterable, relation):
    """Partitions a set of objects into equivalence classes

    Same as equivalence_partition() but also numbers the classes.

    Args:
        iterable: collection of objects to be partitioned
        relation: equivalence relation. I.e. relation(o1,o2) evaluates to True
            if and only if o1 and o2 are equivalent

    Returns: classes, partitions, ids
        classes: A sequence of sets. Each one is an equivalence class
        partitions: A dictionary mapping objects to equivalence classes
        ids: A dictionary mapping objects to the indices of their equivalence classes
    """
    classes, partitions = equivalence_partition(iterable, relation)
    ids = {}
    for i, c in enumerate(classes):
        for o in c:
            ids[o] = i
    return classes, partitions, ids


def check_equivalence_partition(classes, partitions, relation):
    """Checks that a partition is consistent under the relationship"""
    for o, c in partitions.items():
        for _c in classes:
            assert (o in _c) ^ (not _c is c)
    for c1 in classes:
        for o1 in c1:
            for c2 in classes:
                for o2 in c2:
                    assert (c1 is c2) ^ (not relation(o1, o2))


def test_equivalence_partition():
    relation = lambda x, y: (x - y) % 4 == 0
    classes, partitions = equivalence_partition(
        range(-3, 5),
        relation
    )
    check_equivalence_partition(classes, partitions, relation)
    for c in classes: print(c)
    for o, c in partitions.items(): print(o, ':', c)


if __name__ == '__main__':
    test_equivalence_partition()
于 2016-08-12T18:48:24.687 回答
2

我不知道有任何处理等价关系的 python 库。

也许这个片段很有用：

def rel(x1, x2):
   return x1 % 5 == x2 % 5

data = range(18)
eqclasses = []

for x in data:
     for eqcls in eqclasses:
         if rel(x, eqcls[0]):
             # x is a member of this class
             eqcls.append(x)
             break
     else:
         # x belongs in a new class
         eqclasses.append([x])


eqclasses
=> [[0, 5, 10, 15], [1, 6, 11, 16], [2, 7, 12, 17], [3, 8, 13], [4, 9, 14]]
于 2016-08-12T18:51:54.610 回答
2

以下函数采用可迭代a和等价函数equiv，并按照您的要求执行：

def partition(a, equiv):
    partitions = [] # Found partitions
    for e in a: # Loop over each element
        found = False # Note it is not yet part of a know partition
        for p in partitions:
            if equiv(e, p[0]): # Found a partition for it!
                p.append(e)
                found = True
                break
        if not found: # Make a new partition for it.
            partitions.append([e])
    return partitions

例子：

def equiv_(lhs, rhs):
    return lhs % 3 == rhs % 3

a_ = range(10)

>>> partition(a_, equiv_)
[[0, 3, 6, 9], [1, 4, 7], [2, 5, 8]]
于 2016-08-12T18:49:17.377 回答
1 
In [1]: def my_relation(x):
   ...:     return x % 3
   ...:

In [2]: from collections import defaultdict

In [3]: def partition(X, relation):
   ...:     d = defaultdict(list)
   ...:     for item in X:
   ...:         d[my_relation(item)].append(item)
   ...:     return d.values()
   ...:

In [4]: X = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]

In [5]: partition(X, my_relation)
Out[5]: [[3, 6, 9, 12], [1, 4, 7, 10], [2, 5, 8, 11]]

对于二元函数：

from collections import defaultdict
from itertools import combinations

def partition_binary(Y, relation):
    d = defaultdict(list)
    for (a, b) in combinations(Y):
        l = d[my_relation(a, b)]
        l.append(a)
        l.append(b)
    return d.values()

你可以这样做：

partition_binary(partition(X, rank), my_relation)

哦，如果 my_relation 返回一个布尔值，这显然不起作用。我想说想出一些抽象的方式来表示每个同构，尽管我怀疑这是首先尝试这样做的目标。

于 2016-08-12T18:43:47.733 回答
1

这行得通吗？

def equivalence_partition(iterable, relation):
    classes = defaultdict(set)
    for element in iterable:
        for sample, known in classes.items():
            if relation(sample, element):
                known.add(element)
                break
        else:
            classes[element].add(element)
    return list(classes.values())

我试过了：

relation = lambda a, b: (a - b) % 2
equivalence_partition(range(4), relation)

哪个返回：

[{0, 1, 3}, {2}]

编辑：如果您希望它尽可能快地运行，您可以：

  • 将其包装在 Cython 模块中（删除 defaultdict，没有太多需要更改的内容）
  • 想尝试用 PyPy 运行它
  • 找到一个专用模块（找不到任何模块）
于 2016-08-12T18:51:34.400 回答