判断两个列表是否具有相同的元素，无论其顺序如何？

Question

对于这个简单的问题，非常抱歉，但我很难找到答案。

当我比较两个列表时，我想知道它们是否“相等”，也就是说它们具有相同的内容，但是顺序不同。

例如：

x = ['a', 'b']
y = ['b', 'a']

我希望 x == y 能够评估为 True。

- toofly

Answer 1

你可以简单地检查x和y元素的多集是否相等：

import collections
collections.Counter(x) == collections.Counter(y)

这要求元素是可哈希的；运行时复杂度为O(n)，其中n是列表的大小。

如果元素也是唯一的，则可以将其转换为集合（相同的渐进运行时间，在实践中可能会稍微快一些）：

set(x) == set(y)

如果元素不可哈希但可排序，则另一种（运行时为O(n log n)）的替代方法是

sorted(x) == sorted(y)

如果元素既不可哈希也不可排序，可以使用以下辅助函数。请注意，它将非常缓慢（O(n²)），并且通常不应在不可哈希和不可排序的元素的异端情况之外使用。

def equal_ignore_order(a, b):
    """ Use only when elements are neither hashable nor sortable! """
    unmatched = list(b)
    for element in a:
        try:
            unmatched.remove(element)
        except ValueError:
            return False
    return not unmatched

- phihag

---

equal_ignore_order 这个方法不错。我认为，首先检查 a 和 b 的长度是否相等可以改进它。这会稍微加快速度（或者根据输入情况，会大幅加快速度）。 - Jonathan Scholbach

仅使用set(x) == set(y)是不够的。它对于这个问题的特定示例可以工作，但对于其他情况可能会出现错误，例如x = ['a', 'b', 'a']，y = ['b', 'a']。对于这种情况，set(x) == set(y)将返回True，但有人可能会认为它是False。我们必须添加len(x) == len(y)才能完全解决这个问题。然而，使用sorted(x) == sorted(y)就没有这个问题。 - Arman Mojaver

@ArmanMojaver 答案明确提到元素必须是唯一的。 此外，如果存在重复项，则比较长度是无关紧要的。考虑以下情况： x = ['a', 'a', 'b']，y = ['a', 'b', 'b'] set(x) == set(y) 和 len(x) == len(y) 都为 True，但我们可以清楚地看到 x != y。 - AboodXD

Answer 2

确定两个列表的元素是否相同，无论顺序如何？

从您的示例推断：

x = ['a', 'b']
y = ['b', 'a']

为了确保列表中的元素不会重复（它们是唯一的）并且可哈希（像字符串和其他某些不可变的Python对象一样），最直接和计算效率最高的答案使用Python的内置set集合（就像你在学校里学过的数学集合一样）。

set(x) == set(y) # prefer this if elements are hashable

如果元素是可哈希但不唯一的，那么collections.Counter作为一个多集合语义上也是适用的，但速度要慢得多:

from collections import Counter
Counter(x) == Counter(y)

建议使用 sorted：

sorted(x) == sorted(y) 

如果元素可以排序，那么这将考虑到非唯一或非可哈希的情况，但这可能比使用集合慢得多。

实证实验

一项实证实验得出结论：首选set，然后是sorted。只有在需要其他内容（如计数或进一步用作多重集）时才选择Counter。

第一个设置：

import timeit
import random
from collections import Counter

data = [str(random.randint(0, 100000)) for i in xrange(100)]
data2 = data[:]     # copy the list into a new one

def sets_equal(): 
    return set(data) == set(data2)

def counters_equal(): 
    return Counter(data) == Counter(data2)

def sorted_lists_equal(): 
    return sorted(data) == sorted(data2)

测试一下：

>>> min(timeit.repeat(sets_equal))
13.976069927215576
>>> min(timeit.repeat(counters_equal))
73.17287588119507
>>> min(timeit.repeat(sorted_lists_equal))
36.177085876464844

因此我们可以看到，比较集合是最快的解决方案，而比较排序列表是第二快的。

- Russia Must Remove Putin

---

如果你有列表 [1, 1, 8] 和 [1, 8, 8]，那么使用集合是不适用的，因为这些元素实际上是不同的！ - Ian Rehwinkel

@IanRehwinkel 这不是我的回答中显而易见的吗？ - Russia Must Remove Putin

我一定是漏看了那部分。我的错。 - Ian Rehwinkel

Answer 3

这似乎可行，但对于大型列表可能有些繁琐。

>>> A = [0, 1]
>>> B = [1, 0]
>>> C = [0, 2]
>>> not sum([not i in A for i in B])
True
>>> not sum([not i in A for i in C])
False
>>> 

然而，如果每个列表必须包含其他元素，则上述代码存在问题。

>>> A = [0, 1, 2]
>>> not sum([not i in A for i in B])
True

问题出现在当 len(A) != len(B) 时，而在这个例子中，len(A) > len(B)。为了避免这种情况，您可以再添加一个语句。

>>> not sum([not i in A for i in B]) if len(A) == len(B) else False
False

还有一件事，我使用timeit.repeat对我的解决方案进行了基准测试，使用的条件与Aaron Hall在他的帖子中使用的条件相同。正如我所怀疑的那样，结果令人失望。我的方法是最后一个。set(x) == set(y) 就是它了。

>>> def foocomprehend(): return not sum([not i in data for i in data2])
>>> min(timeit.repeat('fooset()', 'from __main__ import fooset, foocount, foocomprehend'))
25.2893661496
>>> min(timeit.repeat('foosort()', 'from __main__ import fooset, foocount, foocomprehend'))
94.3974742993
>>> min(timeit.repeat('foocomprehend()', 'from __main__ import fooset, foocount, foocomprehend'))
187.224562545

- blahreport

---

你的方法是O(N^2)，这并不奇怪，因为它比O(N)或O(N * log N)要大得多。 对于B中的每个元素（N个元素），它都会检查A中的所有元素（N个元素）。因此，检查的次数为N * N。 - RobMcZag

Answer 4

如上评论所述，一般情况下是很麻烦的。如果所有项都是可哈希的或所有项都是可排序的，则相当容易。然而，最近我不得不尝试解决一般情况。这是我的解决方案。发布后我意识到这是一个重复的解决方案，因为我在第一次查看时错过了它。无论如何，如果您使用切片而不是list.remove()，则可以比较不可变序列。

def sequences_contain_same_items(a, b):
    for item in a:
        try:
            i = b.index(item)
        except ValueError:
            return False
        b = b[:i] + b[i+1:]
    return not b

- Grahame