346

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.

1
  • 1
    (Doing this in o(n) space without modifying inputs looks a challenge.) Add ['one', 'one', 'two'] == ['one', 'two', 'two'] to the examples.
    – greybeard
    Sep 9, 2017 at 17:41

8 Answers 8

592

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
>>> 
4
  • 123
    CAUTION: Because using set() removes duplicates this solution returns True instead of False for the third example provided. Mar 8, 2012 at 18:59
  • 5
    this is the best answer if you don't care about duplicates. Suhail's answer stackoverflow.com/a/19244156/403423 is the best if you want to check that they have the identical elements.
    – rbp
    Feb 22, 2014 at 15:12
  • 4
    If you end up here because you have two sets that appear identical but are not evaluating as equal (as I did), check the __hash__ function of those objects to verify that equal objects have equal hashes. Mine did not.
    – Paul Wintz
    Dec 16, 2019 at 12:01
  • 1
    This is not a correct answer, and should not be accepted. sorted(x) == sorted(y) should be the right answer.
    – delimiter
    Apr 30, 2022 at 14:19
77

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.

6
  • 36
    sorted(a) == sorted(b) is my I think the cleanest approach here. I think this answer ought to be the accepted one.
    – Will
    Oct 24, 2013 at 11:05
  • 4
    I don't think this answer is correct because calling sort() on a list may change the sequence of its items, it is unacceptable if we do a comparison of two list and they become different afterwards.
    – Reorx
    Apr 22, 2014 at 6:06
  • 4
    @Reorx: Why the downvote? Have you read: "If you don't want to sort inplace you could use sorted()." in the answer?
    – jfs
    Apr 22, 2014 at 11:35
  • 2
    @J.F.Sebastian Sorry for ignoring that words, but I think a good answer should be explicit and directly tell the reader what is the best way to solve problem, not just provide a controversial way with a dispensable explanation under it. I will withdraw the downvote if you can enhance your answer and tell clearly what's the difference of using .sort() and sorted(). Thank you :)
    – Reorx
    Apr 22, 2014 at 11:43
  • 4
    @Reorx: the best way if you can is to sort inplace: it avoids creating unnecessary copies. It is not always desirable therefore sorted() is mentioned. If you don't know what it does; click the link.
    – jfs
    Apr 22, 2014 at 11:55
60
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.
4
  • @TedKleinBergman They provided attribution, and they did not copy another answer, they converted a useful (+19) comment into an answer. That's valuable. Oct 18, 2019 at 12:49
  • 1
    This is the true answer - and it can handle UNHASHABLE list elements. set() is sometimes not the answer (size, duplication...). Dec 22, 2020 at 17:51
  • 1
    Well, still - it's worth reading Raymond's answer: stackoverflow.com/a/7829388/1338797 - some things, like dicts, are not sortable... Dec 22, 2020 at 18:03
  • 1
    Thanks! this is the most simple yet effective solution. I have just a small set to compare, it is quite fast.
    – Thiago
    Sep 20, 2022 at 4:00
20

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)
4
  • 12
    +1 Good point, I didn't notice that! On the other hand, it doesn't suffice just to check the length (otherwise [1,1,2]==[1,2,2]) -- you have to count up all the objects.
    – Katriel
    Mar 8, 2012 at 19:01
  • 1
    none of these solutions (even the last) will work if you want to check for identical elements (including duplicates)
    – rbp
    Feb 22, 2014 at 15:14
  • 4
    downvote for are_eq([1,2,2],[1,1,2]) == True
    – endolith
    Aug 19, 2015 at 20:23
  • 3
    downvote for are_eq([1,2,2],[1,1,2]) == True
    – eguaio
    Mar 31, 2016 at 14:51
6

Assuming you already know lists are of equal size, the following will guarantee True if and only if two vectors are exactly the same (including order)

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

Example:

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

if you do not want to use the collections library, you can always do something like this: given that a and b are your lists, the following returns the number of matching elements (it considers the order).

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

Therefore,

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

will be True if both lists are the same, contain the same elements and in the same order. False otherwise.

So, you can define the compare function like the first response above,but without the collections library.

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

and

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

One liner answer to the above question is :-

let the two lists be list1 and list2, and your requirement is to ensure whether two lists have the same elements, then as per me, following will be the best approach :-

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

The above piece of code will work per your need i.e. whether all the elements of list1 are in list2 and vice-verse.

But if you want to just check whether all elements of list1 are present in list2 or not, then you need to use the below code piece only :-

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

The difference is, the later will print True, if list2 contains some extra elements along with all the elements of list1. In simple words, it will ensure that all the elements of list1 should be present in list2, regardless of whether list2 has some extra elements or not.

2
  • 2
    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
    Sep 9, 2017 at 17:34
  • This is super slow, O(N^2) complexity Apr 17, 2022 at 12:40
2

What about getting the string representation of the lists and comparing them ?

>>> l1 = ['one', 'two', 'three']
>>> l2 = ['one', 'two', 'three']
>>> l3 = ['one', 'three', 'two']
>>> print str(l1) == str(l2)
True
>>> print str(l1) == str(l3)
False
1
  • 4
    it's two unordered lists.
    – Xiao
    Aug 10, 2015 at 2:42

Not the answer you're looking for? Browse other questions tagged or ask your own question.