Reverse Dictionary. Output keeps changing

Question

So I have to write a function that receives a dictionary as input argument and returns a reverse of the input dictionary where the values of the original dictionary are used as keys for the returned dictionary and the keys of the original dictionary are used as value for the returned dictionary.

For example, if the function is called as

reverse_dictionary({'Accurate': ['exact', 'precise'], 'exact': ['precise'], 'astute': ['Smart', 'clever'], 'smart': ['clever', 'bright', 'talented']})

then my function should return

{'precise': ['accurate', 'exact'], 'clever': ['astute', 'smart'], 'talented': ['smart'], 'bright': ['smart'], 'exact': ['accurate'], 'smart': ['astute']}

Here's my function

def reverse_dictionary(input_dict):
    d={}
    def countEmpty(dictionario):
        count=0
        for k,v in dictionario.items():
            if(len(dictionario[k])==0):
                count+=1
        return count
    def removo(dicto, dicto2):
        for k,v in dicto.items():
            #v.sort()
            if (len(dicto[k])!=0):
                if v[-1] not in dicto2:
                    dicto2[v[-1].lower()]=[k.lower()]
                else:
                    dicto2[v[-1]].append(k.lower())
                dicto[k]=v[:-1]
    while countEmpty(input_dict)<len(input_dict):
        removo(input_dict,d)
    for k,v in d.items():
        v.sort()
    return d

dicta={'astute': ['Smart', 'clever', 'talented'], 'Accurate': ['exact', 'precise'], 'exact': ['precise'], 'talented': ['smart', 'keen', 'Bright'], 'smart': ['clever', 'bright', 'talented']}
print(reverse_dictionary(dicta))

The program initially works. It reverses the dictionary. But the values in the dictionary need to be sorted. I've tested the program with:

dicta={'astute': ['Smart', 'clever', 'talented'], 'Accurate': ['exact', 'precise'], 'exact': ['precise'], 'talented': ['smart', 'keen', 'Bright'], 'smart': ['clever', 'bright', 'talented']}

And it sometimes returns:

{'keen': ['talented'], 'talented': ['astute', 'smart'], 'clever': ['astute', 'smart'], 'exact': ['accurate'], 'bright': ['smart', 'talented'], 'precise': ['accurate', 'exact'], 'smart': ['astute', 'talented']}

Which is the correct answer, but at times it also returns:

{'bright': ['smart', 'talented'], 'exact': ['accurate'], 'talented': ['astute', 'smart'], 'precise': ['accurate', 'exact'], 'clever': ['astute', 'smart'], 'smart': ['astute'], 'keen': ['talented']}

which has the 'smart' key missing the 'talented' value. Even if I have done nothing to change the code. I understand dictionaries in python don't really have any order, but shouldn't the values be consistent? Why does this happen?

Dictionaries are unordered by design. Also, wouldn't it be impossible to decide what to do with `'precise': ['accurate', 'exact']`? Will `accurate` or `exact` become the key? — jDo, Mar 17 '16 at 20:41
You are modifying your dictionary while iterating over it... Not a wise idea — Idos, Mar 17 '16 at 20:41
@jDo They would both become keys with precise as a value for both of them — slau, Mar 17 '16 at 20:45
@slau Someone already asked a question similar to this about the same homework question http://stackoverflow.com/questions/35945473/how-to-reverse-a-dictionary-in-python/35945627#35945627 — DaveBensonPhillips, Mar 17 '16 at 20:51
@HumphreyTriscuit Yeah it's about the same question. However, his/her problem is that the program returns an error. I can't figure out why my program outputs a completely different result even with the same input. — slau, Mar 17 '16 at 21:15
@slau Ok, maybe I've missed something but I don't see that in your output — jDo, Mar 17 '16 at 21:37
Style note: `dict`s have also a `values()` method, so you can replace `for k,v in d.items(): v.sort()` where you have a useless `k` with `for v in d.values(): v.sort()`. BTW: are you using python2 or python3? Because the behaviour of `items` etc changed between the two and it *may* affect the output. — Bakuriu, Mar 17 '16 at 22:19

A.P. · Answer 1 · 2016-03-17T23:15:03.423

You can make a sorted list of tuples associating each value with its key in the original dict, then use itertools.groupby, dict comprehension and list comprehesion to merge the output:

import itertools

d = {'accurate': ['exact', 'precise'],
     'exact': ['precise'], 
     'astute': ['smart', 'clever'],
     'smart': ['clever', 'bright', 'talented']}

l = sorted([(v2,k) for k, v in d.items() for v2 in v])

{k:list(x[1] for x in g) for k, g in itertools.groupby(l, lambda x: x[0])}

Intermediate list l:

[('bright', 'smart'),
 ('clever', 'astute'),
 ('clever', 'smart'),
 ('exact', 'accurate'),
 ('precise', 'accurate'),
 ('precise', 'exact'),
 ('smart', 'astute'),
 ('talented', 'smart')]

Output:

{'bright': ['smart'],
 'clever': ['astute', 'smart'],
 'exact': ['accurate'],
 'precise': ['accurate', 'exact'],
 'smart': ['astute'],
 'talented': ['smart']}

score 0 · Answer 2 · edited May 23 '17 at 12:23

I have been able to reproduce your error of an inconsistent output. There are probably two issues in your algorithm.

You assume that the keys will be iterated over in order.
You are iterating an object while altering it. This is especially weird in Python 3.X where items returns a view of the items rather than an explicit iterable (see this question).

It appears that you can "solve" both of these issues by using the following line:

for k,v in sorted(dicto.items()):

This has provided a consistent, correct output in my tests. I'm not super confident as to why this works, and the lack of explanation might be a statement on why you shouldn't be iterating over a changing object to begin with.

For fun, here's a different, asinine solution:

import networkx as nx

d = {
    'Accurate': ['exact', 'precise'], 
    'exact': ['precise'], 
    'astute': ['Smart', 'clever'], 
    'smart': ['clever', 'bright', 'talented']
}

# make keys uppercase and values lowercase
d = {k.upper(): list(map(str.lower, v)) for k,v in d.items()}

# fill out all of the edges
expanded = nx.convert.to_dict_of_lists(nx.Graph(d))

# convert the uppercase values to lowercase and filter out the uppercase keys
filtered = {k: list(map(str.lower, v)) for k,v in expanded.items() if k.islower()}

alexis · Answer 3 · 2016-03-18T09:35:58.597

You are getting unsorted output because dictionaries are unsorted by design. The only way to see keys in a predictable order is with collections.OrderedDict (a dict replacement), which just shows them in the order they were inserted. You keep getting different outputs every time because the designers of python, as a security measure against denial of service attacks, introduced anon-deterministic component to the order in which the keys are stored and returned.

If the lists of values in your dictionary are already sorted, you can simply sort the keys as you retrieve them:

revdict = reverse_dictionary(dicta)
for k in sorted(revdict):
    print(k, revdict[k])

Or equivalently (since tuples are sorted by first element first):

revdict = reverse_dictionary(dicta)
for k, v in sorted(revdict.items()):
    print(k, v)

Reverse Dictionary. Output keeps changing

3 Answers3