CODEWITHSUNDEEP
pythondictionaryswapin-place
Jonathan
Jonathan

Reputation: 119

In-place Python dictionary inverse

The task that I wanted to see if possible to solve is, swapping key,value pairs of a dictionary (in Python), with an in-place calculation, without additional data-structures (Only a constant number of extra variables). It seems rather impossible (in a finite world), but I'm open to hear suggestions on solving it.

I've seen a few posts about in-place dictionary inverse in python, and I've found one common thing between all of the solutions. The following dictionary won't be properly inversed:

dict = {'b':'a','a':'c','c':123}

The reason for that is, when swapping the first argument, we overwrite 'a''s actual value (The values are unique, the keys are unique, but that doesn't mean there isn't a value that is the same as an already existing key)

NOTES:

1) The dictionary given as an example has hashable values.

2) The key/values can be of any data-type. Not necessarily strings.

I'd love to hear ways to solve it, I've thought of one but it only works if we have infinite memory, which obviously is not true.

EDIT:

1) My Idea was, changing the dictionary such that I add a constant number of underscores ("_") to the beginning of each key entry. The number of underscores is determined based on the keys, if some key has X underscores, I'll add X+1 underscores (max_underscores_of_key_in_prefix+1). To work around objects in the keys, I'll make a wrapper class for that. I have tried my best explaining my intuition, but I am not sure this is practical.

2) @Mark Ransom's solution works perfectly, but if anyone has an other algorithmic solution to the problem, I'd still love to hear it out! I mark this question as solved because it is solved, but again, other solutions are more than welcome :-)

Upvotes: 0

Views: 139

Answers (1)

Mark Ransom
Mark Ransom

Reputation: 308206

Obviously for this to be possible, both keys and values must be hashable. This means that none of your keys or values can be a list. We can take advantage of this to know which dictionary elements have been already processed.

Since you can't iterate and modify a dictionary at the same time, we must start over every time we swap a key/value. That makes this very slow, an O(n^2) operation.

def invert_dict(d):
    done = False
    while not done:
        done = True
        for key, val in d.items():
            if isinstance(val, list):
                if len(val) > 1:
                    d[key] = [val[1]]
                    val = val[0]
            else:
                del d[key]
            if not isinstance(val, list):
                if val in d:
                    d[val] = [d[val], key]
                else:
                    d[val] = [key]
                done = False
                break
    for key, val in d.items():
        d[key] = val[0]

Upvotes: 2

Related Questions