使用python检测等价类

Question

如果给出了两个数字列表，那么检测等价类的最快(最)方法是什么？

对于列表list1 = [1,1,2,3,3,4]和list2 = [5,6,7,7,8,6]，应该有两个等价的类：eqClasses = [[1,4,5,6],[2,3,7,8]]。

Answer 1

为此，您可以使用union-find or disjoint set algorithm。(我总是在附近有一个实现，因为它非常有用。)只需将不同的压缩数字对“联合”，然后获得具有相同“领导者”的数字的“组”。

与问题无关的实现：

class UnionFind:
    def __init__(self):
        self.leaders = collections.defaultdict(lambda: None)

    def find(self, x):
        l = self.leaders[x]
        if l is not None:
            l = self.find(l)
            self.leaders[x] = l
            return l
        return x

    def union(self, x, y):
        lx, ly = self.find(x), self.find(y)
        if lx != ly:
            self.leaders[lx] = ly

    def get_groups(self):
        groups = collections.defaultdict(set)
        for x in self.leaders:
            groups[self.find(x)].add(x)
        return list(groups.values())

应用程序：

list1 = [1,1,2,3,3,4]
list2 = [5,6,7,7,8,6]

uf = UnionFind()
for a, b in zip(list1, list2):
    uf.union(a, b)

print(uf.get_groups())
# [{8, 2, 3, 7}, {1, 4, 5, 6}]

Answer 2

在本例中，如果两个元素出现在两个数组中的相同位置，则这两个元素是等效的。

如果你重新表述这个问题，它会归结为寻找连通子图。您可以将这两个列表转换为成对的等效数字列表。每个数字都可以看作是图中的一个顶点，每对数字都定义了它们之间的边。可以使用简单的广度或深度优先搜索来查找连通子图。Wikipedia说：

在任何一种情况下，从某个特定顶点v开始的搜索将在返回之前找到包含v的整个连通分量(并且不会更多)。要查找图的所有连通分量，请循环遍历其顶点，每当循环到达尚未包含在先前找到的连通分量中的顶点时，就开始新的广度优先或深度优先搜索。

如果您需要一个实用的解决方案，可以使用提供这些算法的软件包。看看NetworkX吧。