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

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

我希望在不使用 map 的情况下完成这个问题。

- KingFish

---

在不修改输入且使用 O(n) 的空间下完成这个任务看起来是一个挑战。将['one', 'one', 'two'] == ['one', 'two', 'two']添加到示例中。 - greybeard

Answer 1

Python内置了一种用于存储（可哈希）元素的无序集合数据类型，称为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
>>> 

- Katriel

---

注意：因为使用set()可以删除重复项，所以该解决方案对于提供的第三个示例将返回True而不是False。 - Michael Whatcott

如果您不关心重复项，那么这就是最佳答案。如果您想检查是否具有相同元素，则Suhail的答案http://stackoverflow.com/a/19244156/403423是最佳答案。 - rbp

如果你在这里因为你有两个看起来相同但判断不等的集合（就像我一样），请检查那些对象的__hash__函数以验证相等的对象具有相等的哈希值。我的没有。 - Paul Wintz

这不是正确的答案，也不应该被接受。sorted(x) == sorted(y) 才是正确的答案。 - delimiter

Answer 2

如果元素总是像你的示例中一样接近排序状态，那么内置的.sort()（timsort）应该很快：

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

如果您不想进行就地排序，可以使用sorted()。

在实践中，它可能总是比collections.Counter()更快（尽管渐近时间复杂度为O(n)的.sort()比O(n*log(n))更好）。要确定，请测量一下。

- jfs

---

我认为"sorted(a) == sorted(b)"是这里最简洁的方法，我认为这个答案应该被采纳。 - Will

我认为这个答案不正确，因为在列表上调用sort()可能会更改其项的顺序，如果我们比较两个列表并且它们之后变得不同，则是不可接受的。 - Reorx

为什么被踩了？你有看到答案中的“如果您不想原地排序，可以使用sorted()”这句话吗？ - jfs

@J.F.Sebastian 对不起，我忽略了那些话，但我认为一个好的答案应该是明确的，直接告诉读者什么是解决问题的最佳方法，而不仅仅提供一种有争议的方式，并在其下面提供一个可有可无的解释。如果您能改进您的答案并清楚地说明使用.sort()和sorted()的区别，我会撤回我的反对票。谢谢 :) - Reorx

如果可能的话，最好采用原地排序的方式：这样可以避免创建不必要的副本。因此，有时并不理想，因此提到了sorted()。如果您不知道它的作用，请单击链接。 - jfs

我认为对于初学者来说，在答案中写sorted更好。.sort()仅适用于大容器以节省内存（它的速度与sorted相比并没有快多少）。 - Mateen Ulhaq

Answer 3

sorted(x) == sorted(y)

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

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

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

- Md Enzam Hossain

---

@TedKleinBergman 他们提供了归属，并且没有复制其他答案，而是将一个有用的（+19）评论转化为了答案。这非常有价值。 - Greg Schmit

这是正确的答案 - 它可以处理不可哈希的列表元素。set()有时并不是最佳选择（大小、重复等问题）。 - Tomasz Gandor

好的，还是值得阅读 Raymond 的回答：https://dev59.com/Umsz5IYBdhLWcg3wiYY0#7829388 - 有些东西，比如 dict，是不可排序的... - Tomasz Gandor

谢谢！这是最简单但最有效的解决方案。我只有一个小集合要比较，速度非常快。 - Thiago

Answer 4

你想要判断两个列表是否包含相同的元素，但不考虑元素的顺序。

你可以使用set：

>>> 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)

- Matimus

---

+1 好观点，我没注意到！另一方面，仅仅检查长度是不够的（否则 [1,1,2]==[1,2,2]）-- 你必须计算所有对象的数量。 - Katriel

即使是最后一种解决方案，如果您想检查相同的元素（包括重复元素），这些解决方案都不会起作用。 - rbp

“downvote” 意为“负投票”，“are_eq([1,2,2],[1,1,2]) == True”的意思是“[1,2,2]”和“[1,1,2]”这两个列表是否相等，答案为True。因此，整句话的意思是：“对于‘are_eq([1,2,2],[1,1,2]) == True’的负投票。” - endolith

针对are_eq([1,2,2],[1,1,2]) == True的投反对票。 - eguaio

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
>>> 

- Arnon Sela

Answer 6

如果您不想使用collections库，您可以尝试以下方法： 假设a和b是您的列表，以下代码将返回匹配元素的数量（考虑顺序）。

sum([1 for i,j in zip(a,b) if i==j])

因此，

len(a)==len(b) and len(a)==sum([1 for i,j in zip(a,b) if i==j])

如果两个列表相同、包含相同的元素并且顺序相同，则为True。否则为False。

因此，您可以像上面的第一个回答那样定义比较函数，但不使用集合库。

compare = lambda a,b: len(a)==len(b) and len(a)==sum([1 for i,j in zip(a,b) if i==j])

并且

>>> compare([1,2,3], [1,2,3,3])
False
>>> compare([1,2,3], [1,2,3])
True
>>> compare([1,2,3], [1,2,4])
False

- fiacobelli

Answer 7

以上问题的简短回答是：

假设有两个列表list1和list2，您的要求是确保这两个列表具有相同的元素，那么我认为以下方法是最好的：

if ((len(list1) == len(list2)) and
   (all(i in list2 for i in list1))):
    print 'True'
else:
    print 'False'

以上代码能够满足您的需求，即判断list1中所有元素是否都在list2中以及反之。

但是，如果您只想检查list1中所有元素是否都存在于list2中，那么您只需要使用以下代码片段：

if all(i in list2 for i in list1):
    print 'True'
else:
    print 'False'

区别在于，如果list2包含除list1元素外的其他元素，则后者将打印True。简单来说，它将确保list2中存在list1的所有元素，无论list2是否有一些额外的元素。

- Pabitra Pati

---

def same(list1, list2): return ((len(list1) == len(list2)) and (all(i in list2 for i in list1))); same((1,1,2), (1,2,2)) - greybeard

这非常慢，复杂度为 O(N^2)。 - Abhishek Divekar

Answer 8

可以尝试获取列表的字符串表示形式并进行比较？

>>> l1 = ['one', 'two', 'three']
>>> l2 = ['one', 'two', 'three']
>>> l3 = ['one', 'three', 'two']
>>> print str(l1) == str(l2)
True
>>> print str(l1) == str(l3)
False

- sagi

---

这是两个“无序列表”。 - Xiao