python - 给定 python 中的关系，是否有一种标准方法可以将可迭代对象划分为等价类？

Question

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

有没有在 python 中执行此操作的标准方法？更好的是，是否有专门用于处理等价关系的模块？

Answer 1

以下函数接受一个可迭代的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]]