Determine if 2 lists have the same elements, regardless of order?

148

Sorry for the simple question, but I'm having a hard time finding the answer.

When I compare 2 lists, I want to know if they are "equal" in that they have the same contents, but in different order.

Ex:

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

I want x == y to evaluate to True.

This question is tagged with python list equality python-2.x

~ Asked on 2012-01-15 00:39:10

The Best Answer is


206

You can simply check whether the multisets with the elements of x and y are equal:

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

This requires the elements to be hashable; runtime will be in O(n), where n is the size of the lists.

If the elements are also unique, you can also convert to sets (same asymptotic runtime, may be a little bit faster in practice):

set(x) == set(y)

If the elements are not hashable, but sortable, another alternative (runtime in O(n log n)) is

sorted(x) == sorted(y)

If the elements are neither hashable nor sortable you can use the following helper function. Note that it will be quite slow (O(n²)) and should generally not be used outside of the esoteric case of unhashable and unsortable elements.

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

~ Answered on 2012-01-15 00:40:53


28

Determine if 2 lists have the same elements, regardless of order?

Inferring from your example:

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

that the elements of the lists won't be repeated (they are unique) as well as hashable (which strings and other certain immutable python objects are), the most direct and computationally efficient answer uses Python's builtin sets, (which are semantically like mathematical sets you may have learned about in school).

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

In the case that the elements are hashable, but non-unique, the collections.Counter also works semantically as a multiset, but it is far slower:

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

Prefer to use sorted:

sorted(x) == sorted(y) 

if the elements are orderable. This would account for non-unique or non-hashable circumstances, but this could be much slower than using sets.

Empirical Experiment

An empirical experiment concludes that one should prefer set, then sorted. Only opt for Counter if you need other things like counts or further usage as a multiset.

First setup:

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)

And testing:

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

So we see that comparing sets is the fastest solution, and comparing sorted lists is second fastest.

~ Answered on 2014-10-02 15:26:45


Most Viewed Questions: