Python – Inversion in nested dictionary
Last Updated :
27 Mar, 2023
Given a nested dictionary, perform inversion of keys, i.e innermost nested becomes outermost and vice-versa.
Input : test_dict = {“a” : {“b” : {}}, “d” : {“e” : {}}, “f” : {“g” : {}} Output : {‘b’: {‘a’: {}}, ‘e’: {‘d’: {}}, ‘g’: {‘f’: {}} Explanation : Nested dictionaries inverted as outer dictionary keys and viz-a-vis. Input : test_dict = {“a” : {“b” : { “c” : {}}}} Output : {‘c’: {‘b’: {‘a’: {}}}} Explanation : Just a single key, mapping inverted till depth.
Method : Using loop + recursion
This is brute way in which this task can be performed. In this, we extract all the paths from outer to inner for each key using recursion and then use this to reverse the ordering in result.
Python3
def extract_path(test_dict, path_way):
if not test_dict:
return [path_way]
temp = []
for key in test_dict:
temp.extend(extract_path(test_dict[key], path_way + [key]))
return temp
def hlper_fnc(test_dict):
all_paths = extract_path(test_dict, [])
res = {}
for path in all_paths:
front = res
for ele in path[::-1]:
if ele not in front :
front[ele] = {}
front = front[ele]
return res
test_dict = {"a" : {"b" : {"c" : {}}},
"d" : {"e" : {}},
"f" : {"g" : {"h" : {}}}}
print("The original dictionary is : " + str(test_dict))
res = hlper_fnc(test_dict)
print("The inverted dictionary : " + str(res))
|
Output
The original dictionary is : {'a': {'b': {'c': {}}}, 'd': {'e': {}}, 'f': {'g': {'h': {}}}}
The inverted dictionary : {'c': {'b': {'a': {}}}, 'e': {'d': {}}, 'h': {'g': {'f': {}}}}
Using a Stack:
Approach:
Initialize a stack with the input dictionary and a None parent key.
Initialize an empty dictionary for the inverted dictionary.
While the stack is not empty:
a. Pop a dictionary d and its parent key parent_key from the stack.
b. Iterate through the items in the dictionary d.
c. If the parent_key is not None, update the inverted dictionary with the current key k as a key, and a dictionary with the parent_key as a key and an empty dictionary as a value.
d. If the current value v is a dictionary, append it to the stack with the current key k as the parent key.
Output the inverted dictionary.
Python3
test_dict = {"a": {"b": {}}, "d": {"e": {}}, "f": {"g": {}}}
stack = [(test_dict, None)]
inverted_dict = {}
while stack:
d, parent_key = stack.pop()
for k, v in d.items():
if parent_key is not None:
inverted_dict.setdefault(k, {}).update({parent_key: {}})
if isinstance(v, dict):
stack.append((v, k))
print(inverted_dict)
|
Output
{'g': {'f': {}}, 'e': {'d': {}}, 'b': {'a': {}}}
This approach has a time complexity of O(n) due to iterating through the dictionary.
The auxiliary space of O(n) to create a new dictionary.
Please Login to comment...