CODEWITHSUNDEEP
pythondictionary
Shawn
Shawn

Reputation: 363

Reversing non-unique dictionary

I have a dictionary that I need reversed and grouped based on non-unique values which is failing based on existing top SO answers.

>>> graph = { 'a': ['car','red'], 'b': ['car','blue'] }
>>> inv_map = {}
>>> for k,v in graph.items():
        inv_map[v] = inv_map.get(v,[])
        inv_map[v].append(k)

TypeError: unhashable type: 'list'

>>> isinstance(graph, dict)
True

Suggestions?

Upvotes: 1

Views: 264

Answers (3)

Shawn
Shawn

Reputation: 363

I found the solution to my problem External Link:

If I am starting with a dict of lists, where lists contain non-unique hashable items, I can create another dict of lists as an inverse:

def invert_dol_nonunique(d):
    newdict = {}
    for k in d:
        for v in d[k]:
            newdict.setdefault(v, []).append(k)
    return newdict

Upvotes: 1

abarnert
abarnert

Reputation: 365767

If you want to use each element of each list as a key (which seems more useful), see wim's answer.

If you actually do want to map the values themselves to keys—well, you can't do that, because, as the error tells you, lists aren't hashable. This is because lists are mutable, but they compare by equality, which means your key could change value after you put it in the dict, and that would break the dict.

If you want to compare lists by equal value, rather than by identity, you can do that by using tuples instead. They work as dict keys because they're immutable:

for k,v in graph.items():
    t = tuple(v)
    inv_map[t] = inv_map.get(t,[])
    inv_map[t].append(k)

If you want to compare lists by identity, rather than value (which is much less common, but still sometimes useful), you can use their ids as keys:

for k,v in graph.items():
    i = id(v)
    inv_map[i] = inv_map.get(i,[])
    inv_map[i].append(k)

Of course either way, whenever you want to look something up, you have to convert explicitly:

val = ['car', 'ref']
keys = inv_map_tup[tuple(val)]
keys = inv_map_id[id(val)]

If you're going to be doing a lot of that, you may want to get a "transformdict" off PyPI or the ActiveState recipe collection, or build one yourself.1 If you only care about this simple use, it can be a pretty simple wrapper around dict that calls a function on the key before each operation. For example:

def __getitem__(self, key):
    return super().__getitem__(self.transformer(key))
def __setitem__(self, key, value):
    super().__setitem__(self.transformer(key), value)
# etc.

Then you can just make a transformdict(tuple) or transformdict(id).

1. I don't have a recommendation for a specific one, but PEP 455, a rejected proposal to add one to the stdlib, has links to multiple implementations, and a proposed "reference implementation" for the stdlib, and detailed discussion about the idea.

Upvotes: 1

wim
wim

Reputation: 362786

Since the values are lists, you'll need to iterate those lists to accumulate keys:

from collections import defaultdict
inv_map = defaultdict(list)

for k, vs in graph.items():
    for v in vs:
        inv_map[v].append(k)

inv_map.default_factory = None  # quack like a normal dict

Upvotes: 2

Related Questions