How to efficiently compare two unordered lists (not sets) in Python?

python algorithm list comparison
johndir picture johndir · Oct 20, 2011 · Viewed 79.7k times · Source 
a = [1, 2, 3, 1, 2, 3]
b = [3, 2, 1, 3, 2, 1]

a & b should be considered equal, because they have exactly the same elements, only in different order.

The thing is, my actual lists will consist of objects (my class instances), not integers.

Answer

Raymond Hettinger picture Raymond Hettinger · Oct 20, 2011

O(n): The Counter() method is best (if your objects are hashable):

def compare(s, t):
    return Counter(s) == Counter(t)

O(n log n): The sorted() method is next best (if your objects are orderable):

def compare(s, t):
    return sorted(s) == sorted(t)

O(n * n): If the objects are neither hashable, nor orderable, you can use equality:

def compare(s, t):
    t = list(t)   # make a mutable copy
    try:
        for elem in s:
            t.remove(elem)
    except ValueError:
        return False
    return not t

Related questions

Removing duplicates in the lists

Pretty much I need to write a program that checks if a list has any duplicates and if it does it removes them and returns a new list with the items that weren't duplicated/removed. This is what I have …

Read More
Permutations between two lists

I’m having trouble wrapping my head around a algorithm I’m try to implement. I have two lists and want to take particular combinations from the two lists. Here’s an example. names = 'a', 'b' numbers = 1, 2 the output in …

Read More
Pythonic way to check if a list is sorted or not

Is there a pythonic way to check if a list is already sorted in ASC or DESC listtimestamps = [1, 2, 3, 5, 6, 7] something like isttimestamps.isSorted() that returns True or False. I want to input a list of timestamps for some messages and check …

Read More