Coder Perfect

Compare two unordered lists to see if they’re the same [duplicate].


I’m searching for a simple (and quick) approach to see if two unordered lists have the same components in them:

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 avoid utilizing a map for this.

Asked by Paul

Solution #1

A set is a Python built-in datatype for an unordered collection of (hashable) items. The comparison will be unordered if both lists are converted to sets.

set(x) == set(y)

Documentation on set

EDIT: @mdwhatcott suggests that you check for duplication. Because set ignores these, you’ll need a data structure that maintains track of the number of items in each list as well. A multiset is the best approximation in the standard library; 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])
>>> compare([1,2,3], [1,2,3])
>>> compare([1,2,3,3], [1,2,2,3])

Answered by Katriel

Solution #2

If components are almost sorted all of the time, as in your case, the builtin.sort() (timsort) function should be quick:

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

You might use sorted instead of sorting in place if you don’t want to sort in place ().

In practice, it is possible that it will always be faster than collections. Counter() (despite the fact that O(n) time is asymptotically better than O(n*log(n) for.sort()). If it’s important, measure it.

Answered by jfs

Solution #3

sorted(x) == sorted(y)

Taking a page from here: Compare two unordered lists to see if they’re the same.

This, I believe, is the finest response to this topic because

Answered by Md Enzam Hossain

Solution #4

You’re only interested in seeing if they have the same elements, not the order.

You can make use of a set:

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

The set object, on the other hand, will only have one instance of each unique value and will not maintain order.

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

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)

Answered by Matimus

Solution #5

Assuming you already know that lists of equal size exist, the following guarantees True if and only if two vectors are identical (including order)

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


>>> 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])
>>> compvecs(a=[1,2,3,4], b=[1,2,3,4])
>>> compvecs(a=[1,2,3,4], b=[1,2,4,3])
>>> compare_vectors(a=[1,2,3,4], b=[1,2,2,4])

Answered by Arnon Sela

Post is based on