Inverting a dictionary with sets/lists as values

Viewed 60

I have written a function to invert a dictionary (checked against many other StackExchange posts about similar tasks) whose keys are strings and whose values are sets (of strings):

def invert_dict(d: Dict[str, set]) -> Dict[str, set]:
    """
    Returns inverted dictionary (with original dictionary, d, whose keys are
    strings and values are sets containing strings of which occur in the
    keys of d).

    Useful for indexing graph in opposite direction (i.e., values inbound to
    key vs. values outbound to key).
    """
    inverse_dict = dict.fromkeys(d, set())
    for key in d.keys():
        for item in d[key]:
            inverse_dict[item].add(key)

    return inverse_dict

What I am finding to be completely mind-boggling is that adding a string to one value/set (associated with one particular key) actually adds said string to all values/sets in the resultant dictionary!

Per the code above, the troublemaking line is inverse_dict[item].add(key).

For example, consider the following dictionary:

original_dict = {'4.html': {'2.html'}, 
                 '3.html': {'4.html', '2.html'}, 
                 '2.html': {'3.html', '1.html'}, 
                 '1.html': {'2.html'}}

When I add print statements before and after inverse_dict[item].add(key) and run invert_dict(original_dict), I get the following printed to console:

Adding 4.html to the set associated with 2.html
{'4.html': {'4.html'}, '3.html': {'4.html'}, '2.html': {'4.html'}, '1.html': {'4.html'}}

Adding 3.html to the set associated with 4.html
{'4.html': {'3.html', '4.html'}, '3.html': {'3.html', '4.html'}, '2.html': {'3.html', '4.html'}, '1.html': {'3.html', '4.html'}}

Adding 3.html to the set associated with 2.html
{'4.html': {'3.html', '4.html'}, '3.html': {'3.html', '4.html'}, '2.html': {'3.html', '4.html'}, '1.html': {'3.html', '4.html'}}

Adding 2.html to the set associated with 3.html
{'4.html': {'3.html', '4.html', '2.html'}, '3.html': {'3.html', '4.html', '2.html'}, '2.html': {'3.html', '4.html', '2.html'}, '1.html': {'3.html', '4.html', '2.html'}}

Adding 2.html to the set associated with 1.html
{'4.html': {'3.html', '4.html', '2.html'}, '3.html': {'3.html', '4.html', '2.html'}, '2.html': {'3.html', '4.html', '2.html'}, '1.html': {'3.html', '4.html', '2.html'}}

Adding 1.html to the set associated with 2.html
{'4.html': {'1.html', '3.html', '4.html', '2.html'}, '3.html': {'1.html', '3.html', '4.html', '2.html'}, '2.html': {'1.html', '3.html', '4.html', '2.html'}, '1.html': {'1.html', '3.html', '4.html', '2.html'}}

What gives? I have tried replacing d.keys() with d.items() and using lists instead of sets, but the results were the same.

I am using Python 3.7.6.

1 Answers

dict.fromkeys(d, set()) just creates one set and puts that in every dictionary entry. You need to create a new set for each entry:

inverse_dict = {k: set() for k in d}
Related