Using Lists with Sets (Unhashable Type error)

Question

So I am trying to use a set to keep track of tuples that contain a tuple and a list of tuples. Here is an example of what is in the set before the error:

((1, 16), [(1, 1), (1, 13), (1, 14), (1, 15), (1, 18), (2, 1), (2, 4),  (2, 7), (2, 10), (2, 13), (2, 18), (3, 6), (3, 7), (3, 8), (3, 9), (3, 10), (3, 18)])

Here is the error I get:

Traceback (most recent call last):
File "src/graph.py", line 60, in <module>
end_node, A_expanded = A_search_multiple(maze,start,dot_locs)
 File "/home/lstrait2/cs440/mp1/src/search_multiple.py", line 37, in      A_search_multiple
if((loc,state) not in closed):
 TypeError: unhashable type: 'list'
[lstrait2@linux-a2 mp1]$ gedit src/search_multiple.py

Is there anything I can do to make this work? Basically I am using the set to make sure no tuple of the form (location, list of locations) appears twice.

What are loc and state? Presumably one or both is a list, so should be converted to tuple first. — jonrsharpe
– jonrsharpe, Commented Feb 18, 2015 at 17:16
Then you will need if (loc, tuple(state)) not in closed: (note the unnecessary parentheses have been removed). — jonrsharpe
– jonrsharpe, Commented Feb 18, 2015 at 17:23

Travis Griggs · Accepted Answer · 2015-02-18 17:56:35Z

2

Short answer:

You have to convert your list into a tuple. It is legal to have a tuple of tuples (nested tuples).

Why is this?

Sets and Dictionaries work on a principle of uniqueness. At the time values are added to them, they determine if they already contain a value of equal nature. That is the only time the container has the opportunity to enforce its invariant of unique elements. Lists can certainly be compared for equality, but the problem is that they can change. Let us pretend that you could add lists to a set. Consider the following example:

list1 = [42]
list2 = [42, 13]
list1 == list2 # this would show false, they're different lists, obviously
mySet = set()
mySet.add(list1) # python won't allow this, but we're pretending it would
mySet.add(list2) # ditto

If we printed mySet at this point, we'd expect to something like:

{[42, 13], [42]}

But we can change lists, so what if we now executed:

list1.append(13)
list1 == list2 # This used to be false, but now it is true

Unbeknownst to the containing set, outside of it's awareness, two of its elements have suddenly become equal. Now we've violated the invariant that a set's elements should be unique.

To avoid this problem, dicts and sets won't allow you to stick objects in them that it knows have a predisposition to changing.

answered Feb 18, 2015 at 17:56

Travis Griggs

22.4k22 gold badges106 silver badges177 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

sharshofski Over a year ago

Probably a duplicate of stackoverflow.com/questions/19371358/…

Collectives™ on Stack Overflow

Using Lists with Sets (Unhashable Type error)

1 Answer 1

1 Comment

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Linked

Related