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
# Python3 code to demonstrate working of # Inversion in nested dictionary# Using loop + recursion# utility function to get all paths till end 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# function to compute inversiondef 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# initializing dictionarytest_dict = {"a" : {"b" : {"c" : {}}}, "d" : {"e" : {}}, "f" : {"g" : {"h" : {}}}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# calling helper function for task res = hlper_fnc(test_dict)# printing result print("The inverted dictionary : " + str(res)) |
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
# Sample input dictionarytest_dict = {"a": {"b": {}}, "d": {"e": {}}, "f": {"g": {}}}# Invert the nested dictionary using a stackstack = [(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))# Output the inverted dictionaryprint(inverted_dict) |
{'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.
