Check if two unordered lists are equal [duplicate]

Question

I'm looking for an easy (and quick) way to determine if two unordered lists contain the same elements:

For example:

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

I'm hoping to do this without using a map.

Answer 1

Python has a built-in datatype for an unordered collection of (hashable) things, called a set. If you convert both lists to sets, the comparison will be unordered.

set(x) == set(y)

Documentation on set

---

EDIT: @mdwhatcott points out that you want to check for duplicates. set ignores these, so you need a similar data structure that also keeps track of the number of items in each list. This is called a multiset; the best approximation in the standard library is a 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

If elements are always nearly sorted as in your example then builtin .sort() (timsort) should be fast:

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

If you don't want to sort inplace you could use sorted().

In practice it might always be faster then collections.Counter() (despite asymptotically O(n) time being better then O(n*log(n)) for .sort()). Measure it; If it is important.

Answer 3

sorted(x) == sorted(y)

Copying from here: Check if two unordered lists are equal

I think this is the best answer for this question because

1. It is better than using counter as pointed in this answer
2. x.sort() sorts x, which is a side effect. sorted(x) returns a new list.

Answer 4

You want to see if they contain the same elements, but don't care about the order.

You can use a set:

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

But the set object itself will only contain one instance of each unique value, and will not preserve order.

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

So, if tracking duplicates/length is important, you probably want to also check the length:

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