如何检查两个列表是否与重复列表相等？

Question

我试图比较Python中的两个列表，检查它们是否相同。问题是，这两个列表都可以包含重复的元素，为了被认为是相等的，它们需要有相同数量的重复元素。

目前，我已经“解决”了这一问题，方法是创建两个列表的副本，如果两个列表相等，则从它们中删除一个元素：

def equals(v1: Vertex, v2: Vertex) -> bool:
    # also checks if neighbourhoods are the same size
    if v1.label == v2.label:

        # copy the neighbourhoods to prevent data loss on removal of checked vertices
        v1_neighbours = v1.neighbours.copy()
        v2_neighbours = v2.neighbours.copy()

        # for every Vertex in v1.neighbours, check if there is a corresponding Vertex in v2.neighbours
        # if there is, remove that Vertex from both lists
        for n1 in v1_neighbours:
            for n2 in v2_neighbours:
                if n1.label == n2.label:
                    v1_neighbours.remove(n1)
                    v2_neighbours.remove(n2)
                    break
                else:
                    return False

        if len(v1_neighbours) == 0 and len(v2_neighbours) == 0:
            return True

    return False

我怀疑这个解决方案是否有效：List.remove(element)没有删除该元素的所有出现吗？此外，我不认为它的内存效率，这是重要的，因为社区将是相当大的。

有人能告诉我如何正确地比较v1_neighbours和v2_neighbours，在不复制列表的情况下，在不改变列表的情况下检查相同数量的副本吗？

Answer 1

数一数和比较计数器：

a= [ (x,y) for x in range(5) for y in range(5)]+[ (x,y) for x in range(3) for y in range(3)]
b= [ (x,y) for x in range(5) for y in range(5)]+[ (x,y) for x in range(3) for y in range(3)]
c= [ (x,y) for x in range(5) for y in range(5)]+[ (x,y) for x in range(4) for y in range(3)]

from collections import Counter

ca = Counter(a)
cb = Counter(b)
cc = Counter(c)

print(ca==cb)    # True
print(ca==cc)    # False
print(ca)

输出：

True
False

Counter({(0, 0): 2, (0, 1): 2, (0, 2): 2, (1, 0): 2, (1, 1): 2, (1, 2): 2, 
         (2, 0): 2, (2, 1): 2, (2, 2): 2, (0, 3): 1, (0, 4): 1, (1, 3): 1, 
         (1, 4): 1, (2, 3): 1, (2, 4): 1, (3, 0): 1, (3, 1): 1, (3, 2): 1, 
         (3, 3): 1, (3, 4): 1, (4, 0): 1, (4, 1): 1, (4, 2): 1, (4, 3): 1, 
         (4, 4): 1})

Answer 2

虽然collections.Counter将是在Python中执行这种多集比较的通常方法，但我认为比较邻居是对顶点相等测试的一种根本错误的方法。根据程序的详细信息，顶点相等应该使用默认的基于标识的相等或基于标签的相等。

您似乎在尝试实现一个比较，如果两个顶点具有相同的标签和相同的邻居集合，那么它们是相等的。但是，如果两个不同的顶点有可能有相等的标号，那么两个不同的顶点应该有相同的标号和相同的邻居，这是一个不一致的比较。如果两个顶点不可能有相同的标签，那么比较邻居是不必要的。

邻居比较嵌套循环还假定，如果有相同的标签，则顶点是相等的，从而进一步支持基于标签的比较。如果这个假设是错误的，那么你就有了如何确定邻居是否相等的问题。如果尝试将邻居与==进行比较，就会遇到无限递归。

有了额外的澄清，您正在实现一个颜色细化算法，我们可以确认，通过标签比较邻居实际上是正确的。但是，对于您正在实现的函数来说，equals似乎是一个误导的名称，因为您没有测试给定的顶点对象是否代表相同的顶点。