Assert list of list equality without order in Python

Question

What's the best way to assert two lists of lists are equal without importance of order? e.g. these two lists are equal:

a = [[1,2], [3,4]]
b = [[4,3], [2,1]]

assert lists_equal_without_order(a, b)  # True

How can lists_equal_without_order be implemented, ideally with using some of Python's existing assertions?

Answer 1

One version that only works with a bunch of assumptions:

def lists_equal_without_order(a, b):
    """
    We don't care about duplicates in list comparison or the sublist comparison.
    * [1,2,2] === [1,1,2]  # True
    * [[1,1], [1,1]] == [[1,1]] # True
    The element lists are either the same length or we don't care about duplicates
    * [1,1,1] === [1]  # True
    """
    for l1 in a:
        check_list = frozenset(l1)
        if not any(check_list.issuperset(l2) for l2 in b):
            return False
    return True

a = [[1,2], [3,4]]
b = [[4,3], [2,1]]

print lists_equal_without_order(a, b)  # True

a = [[1,1], [2,2]]
b = [[1,2], [2,1]]

print lists_equal_without_order(a, b)  # False

One version that messes up the original list:

def lists_equal_without_order(a, b):
    """
    This will manipulate the original lists.
    """
    for l1 in a:
        l1.sort()
        for l2 in b:
            l2.sort()
            if l1 == l2:
                b.remove(l2)
                break
        else:
            return False
    return True

a = [[1,2], [3,4]]
b = [[4,3], [2,1]]

print lists_equal_without_order(a, b)  # True

a = [[1,1], [2,2]]
b = [[1,2], [2,1]]

print lists_equal_without_order(a, b)  # False

One version that does an exact match with counters, but doesn't need to keep 2 copies of the lists in memory:

from collections import Counter

def lists_equal_without_order(a, b):
    """
    This will make sure the inner list contain the same, 
    but doesn't account for duplicate groups.
    """
    for l1 in a:
        check_counter = Counter(l1)
        if not any(Counter(l2) == check_counter for l2 in b):
            return False
    return True

a = [[1,2], [3,4]]
b = [[4,3], [2,1]]

print lists_equal_without_order(a, b)  # True

a = [[1,1], [2,2]]
b = [[1,2], [2,1]]

print lists_equal_without_order(a, b)  # False

Answer 2

If there are no duplicates in the items in a or b, then you could use a set comprehension to collect the frozen set of each item. For example,

In [106]: {(frozenset(item)) for item in a}
Out[106]: {frozenset({1, 2}), frozenset({3, 4})}

Then test if these sets are equal:

In [107]: {(frozenset(item)) for item in a} == {(frozenset(item)) for item in b}
Out[107]: True

---

This works because sets have no order, and frozensets are hashable (and therefore can be elements of a set). If there are no duplicates, then frozenset equality makes [1,2] and [2,1] equivalent:

In [109]: frozenset([1,2]) == frozenset([2,1])
Out[109]: True

But note that if there are duplicates, then frozensets would make [1,1,2] equivalent to [2,2,1]:

In [108]: frozenset([1,1,2]) == frozenset([1,2,2])
Out[108]: True

Answer 3

If there are no duplicates in the sublists (or duplicates can be ignored), this approach works:

def lists_equal_without_order(a, b):
    return set_repr(a) == set_repr(b)

def set_repr(x):
    return {frozenset(item) for item in x}

---

If we need to account for duplicates within the sublists, we need to use Counters instead of frozensets:

from collections import Counter

def lists_equal_without_order(a, b):
    return counter_repr(a) == counter_repr(b)

def counter_repr(x):
    return {frozenset(Counter(item).items()) for item in x}

---

If the sublists themselves can occur multiple times (i.e. if the outer list contains duplicates), we can use a Counter for the outer list:

from collections import Counter

def lists_equal_without_order(a, b):
    return counter_repr(a) == counter_repr(b)

def counter_repr(x):
    return Counter(frozenset(Counter(item).items()) for item in x)

Answer 4

If performance is not a factor, A simple solution would be to first sort the inner lists, and then sort the outer lists, and then compare them.

Example -

def lewo(l1, l2):
    l1new = [sorted(i) for i in l1]
    l2new = [sorted(i) for i in l2]
    l1newsorted = sorted(l1new)
    l2newsorted = sorted(l2new)
    return l1newsorted == l2newsorted

Or more tersely -

def lewo(a, b):
    a_s, b_s = map(sorted, a), map(sorted, b)
    return sorted(a_s) == sorted(b_s)