2
\$\begingroup\$

For the below question picked from here:

Write make_inverse_dict(d) that returns a new dictionary with the 'inverse' mapping. The 'inverse' mapping of a dictionary d is a new dictionary that maps each of d's values to all keys in d that mapped to it. For instance:

>>> d1 = {'call': 3, 'me': 2, 'maybe': 3}
>>> d2 = make_inverse_dict(d1)
>>> d2  # note that we know nothing about the order of dictionaries
{3: ('maybe', 'call'), 2: ('me',)}

The ordering of the tuple of keys doesn't matter, i.e., d2 could have instead been {3: ('call', 'maybe'), 2: ('me',)}.

Below is the solution:

d1 = {'me': 2, 'call': 3, 'may be': 3}

def make_inverse_dict(d1):
    d2 = {}
    for key in d1:
        if d2.get(d1[key]) == None:
           d2[d1[key]] = (key,)
        else:
            d2[d1[key]] += (key,)
    return d2

d2 = make_inverse_dict(d1)  

Additionally this is the recursive solution:

d1 = {'me': 2, 'call': 3, 'may be': 3} 
def isEmpty(dictionary):
    for element in dictionary:
        if element:
            return False
    return True


def make_inverse_dict_recur(d1):
    temp = {}
    def make_inverse_dict():
        if not isEmpty(d1):
            tup = d1.popitem()
            if temp.get(tup[1]) == None:
                temp[tup[1]] = (tup[0], )
            else:
                temp[tup[1]] += (tup[0], )          
            make_inverse_dict()
    make_inverse_dict()
    return temp

d2 = make_inverse_dict_recur(d1.copy())

Can we improve these solutions?

\$\endgroup\$
2
  • \$\begingroup\$ (Deleted my answer, as it was misleading. -- sorry :)) In general, try to use list comprehensions and generators if you can. There are some interesting utilities in the itertools package that might help you. \$\endgroup\$ May 7, 2015 at 7:47
  • \$\begingroup\$ For more speed and readability, don't iterate over just the keys, iterate over keys and values at the same time for key, value in dict.items() or for key, value in dict.iteritems() (Python2). \$\endgroup\$ May 7, 2015 at 7:52

2 Answers 2

3
\$\begingroup\$

I think the recursive approach, using a nested function, is a bit awkward. I tend to avoid reliance on closures ("explicit is better than implicit", after all!) and use explicit parameters instead.


To create a temp dictionary only on the top level call, I would use:

def recur_func(..., temp=None):
    if temp is None:
        temp = {}
    ...
    recur_func(..., temp)

(if you're wondering why not temp={} in the parameter list, see "“Least Astonishment” in Python: The Mutable Default Argument")


Rather than tup = d1.popitem() then indexing into the tuple, I would use key, val = d1.popitem(); this improves the readability of subsequent lines, as e.g. key is much more informative than tup[0]. You can also use dict.setdefault (or, as pointed out in Günther's answer, collections.defaultdict) to neaten up the logic:

key, val = d1.popitem()
temp.setdefault(val, []).append(key)

That just leaves factoring out the nested function, and making make_inverse_dict_recur directly recursive:

def make_inverse_dict_recur(d1, temp=None):
    if temp is None:
        temp = {}
    if not isEmpty(d1):  # why not just 'if d1:'?
        key, val = d1.popitem()
        temp.setdefault(val, []).append(key)        
        make_inverse_dict_recur(d1, temp)
    return temp

Again, though, contrast that with the iterative version:

def make_inverse_dict_iter(d1):
    temp = {}
    for key, val in d1.items():
        temp.setdefault(val, []).append(key)
    return temp

This has the neat advantage of not mutating d1; generally, Python functions should either mutate their arguments or return a new object, not both. I suspect that this would be (at best) tricky to achieve with a recursive approach, though.

\$\endgroup\$
2
0
\$\begingroup\$

Some hints:

  • Iterate over dictionaries using for key, value in d.items() (or iteritems() in Python2.
  • Consider using a collections.defaultdict(list) as output dictionary. Then you can append unconditionally.
  • When appending to arrays, don't use d += (key,), but just d.append(key).
  • Try looking into the itertools package. This one has interesting combinators for generators that can make your code very concise.
  • Prefer list and dict comprehensions if you can.
\$\endgroup\$
4
  • \$\begingroup\$ how do I think of recursive approach for the same? \$\endgroup\$ May 7, 2015 at 8:01
  • \$\begingroup\$ i think d.extend(key) is better than d.append(key) \$\endgroup\$ May 7, 2015 at 8:05
  • 1
    \$\begingroup\$ extend and append do different things; append only adds one item, extend appends another list (or more generally, a sequence) at the end. \$\endgroup\$ May 7, 2015 at 11:37
  • \$\begingroup\$ extend will be a problem if isinstance(key, str) and len(key) > 1, for example... \$\endgroup\$
    – jonrsharpe
    May 7, 2015 at 12:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.