Unordered collection for unhashable objects?

Question

I've got a dict where some of the values are not hashable. I need some way to compare two unordered groups of these to ensure they contain equal elements. I can't use lists because list equality takes the order into account but sets won't work because dicts aren't hashable. I had a look through the python docs, and the only thing that looks useful is a dict's view, which is hashable under some circumstances but in this case this doesn't help either as one of the values is an object which contains lists itself, meaning the dict's view won't be hashable either.

Is there a standard container for situations like this, or should I just use lists and loop through every element in both lists and ensure an equal element is somewhere in the other list?

Answer 1

When duplicate entries don't exist, the usual choices are:

1. If the elements are hashable: set(a) == set(b)

2. If the elements are orderable: sorted(a) == sorted(b)

3. If all you have is equality: len(a) == len(b) and all(x in b for x in a)

If you have duplicates and their multiplicity matters, the choices are:

1. If the elements are hashable: Counter(a) == Counter(b)

2. If the elements are orderable: sorted(a) == sorted(b)

3. If all you have is equality: len(a) == len(b) and all(a.count(x) == b.count(x) for x in a)

Answer 2

I think the simplest method is to use lists.

group_1 = my_dict_1.values()
group_2 = my_dict_2.values()

Your comparison won't be as simple as if order mattered, or if the values were hashable, but the following should work:

def contain_the_same(group_1, group_2):
    for item in group_1:
        if item not in group_2:
            return False
        else:
            group_2.pop(group_2.index(item))
    if len(group_2) != 0:
        return False
    return True

This should be able to handle unhashable objects just fine:

>>> contain_the_same([1,2,3], [1,2,3])
True
>>> contain_the_same([1,2,3], [1,2,3,4])
False
>>> contain_the_same([1,2,[3,2,1]], [1,2,[3,2,1]])
True
>>> contain_the_same([5,1,2,[3,2,1,[1]]], [1,[3,2,1,[1]],2,5])
True

A caveat: This will return false if there are duplicates in one list, but no the other. This would require some modification if you wanted to make that an allowable case.

Edit: Even easier:

sorted(my_dict_1.values()) == sorted(my_dict_1.values())

It even looks like this is twice as fast as my contain_the_same function:

>>> timeit("contain_the_same([5,1,2,[3,2,1,[1]]], [1,[3,2,1,[1]],2,5])", 
           "from __main__ import contain_the_same", number=10000)/10000
8.868489032757054e-06
>>>timeit("sorted([5,1,2,[3,2,1,[1]]]) == sorted([1,[3,2,1,[1]],2,5])",
           number=10000)/10000
4.928951884845034e-06

Although it would not be as easy to extend to the case where duplicates are allowed.