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

toofly picture toofly · Jan 15, 2012 · Viewed 143.5k times · Source

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.

Answer

phihag picture phihag · Jan 15, 2012

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