检查两个无序列表是否相等

Question

我正在寻找一种简单(快速)的方法来确定两个无序列表是否包含相同的元素:

例如:

['one', 'two', 'three'] == ['one', 'two', 'three'] :  true
['one', 'two', 'three'] == ['one', 'three', 'two'] :  true
['one', 'two', 'three'] == ['one', 'two', 'three', 'three'] :  false
['one', 'two', 'three'] == ['one', 'two', 'three', 'four'] :  false
['one', 'two', 'three'] == ['one', 'two', 'four'] :  false
['one', 'two', 'three'] == ['one'] :  false

我希望不使用地图就能做到这一点.

Answer 1

Python有一个内置的数据类型,用于无序的(可散列)事物集合,称为a set.如果将两个列表都转换为集合,则比较将是无序的.

set(x) == set(y)

关于的文件 set

编辑:@mdwhatcott指出您要检查重复项.set忽略这些,所以你需要一个类似的数据结构,它也跟踪每个列表中的项目数.这被称为multiset ; 标准库中的最佳近似值是collections.Counter:

>>> import collections
>>> compare = lambda x, y: collections.Counter(x) == collections.Counter(y)
>>> 
>>> compare([1,2,3], [1,2,3,3])
False
>>> compare([1,2,3], [1,2,3])
True
>>> compare([1,2,3,3], [1,2,2,3])
False
>>> 

Answer 2

如果元素总是按照您的示例进行排序,那么builtin .sort()(timsort)应该很快:

>>> a = [1,1,2]
>>> b = [1,2,2]
>>> a.sort()
>>> b.sort()
>>> a == b
False

如果你不想在现场排序,你可以使用sorted().

在实践中它可能永远是那么快collections.Counter()(尽管渐进O(n)时间是更好,然后O(n*log(n))进行.sort()).测量它; 如果重要的话.

Answer 3

sorted(x) == sorted(y)

从这里复制:检查两个无序列表是否相等

我认为这是这个问题的最佳答案,因为

1. 这比在这个答案中指出的使用计数器更好
2. x.sort()对x进行排序,这是一种副作用.sorted(x)返回一个新列表.

Answer 4

您想要查看它们是否包含相同的元素,但不关心顺序.

你可以使用一套:

>>> set(['one', 'two', 'three']) == set(['two', 'one', 'three'])
True

但是set对象本身只包含每个唯一值的一个实例,并且不会保留顺序.

>>> set(['one', 'one', 'one']) == set(['one'])
True

因此,如果跟踪重复项/长度很重要,您可能还需要检查长度:

def are_eq(a, b):
    return set(a) == set(b) and len(a) == len(b)

Answer 5

假设您已经知道列表大小相等，当且仅当两个向量完全相同（包括顺序）时，以下内容将保证 True

functools.reduce(lambda b1,b2: b1 and b2, map(lambda e1,e2: e1==e2, listA, ListB), True)

例子：

>>> from functools import reduce
>>> def compvecs(a,b):
...     return reduce(lambda b1,b2: b1 and b2, map(lambda e1,e2: e1==e2, a, b), True)
... 
>>> compvecs(a=[1,2,3,4], b=[1,2,4,3])
False
>>> compvecs(a=[1,2,3,4], b=[1,2,3,4])
True
>>> compvecs(a=[1,2,3,4], b=[1,2,4,3])
False
>>> compare_vectors(a=[1,2,3,4], b=[1,2,2,4])
False
>>>