Given a dictionary, the task is to formulate a python program to re-assign it using a path relation among its keys and values, i.e value of one key is key to another.
Example:
Input : test_dict = {3 : 4, 5 : 6, 4 : 8, 6 : 9, 8 : 10}
Output : {3: 10, 5: 9, 4: 10, 6: 9, 8: 10}
Explanation : key 3 has value 4. key 4 has value 8. key 8 has value 10. there is no key 10 thus in the new dictionary key will have value 10.Similarly, key 5 has value 6. key 6 has value 9. There is no key 9 hence in the new dictionary key 5 will have value 9.
Method 1: Using loop and keys()
In this, we iterate for each key and find its depth, by using external function for repeated checking for each value being key of other item in dictionary.
Python3
def find_depth(ele, dicti): # finding depth for idx in range(len(list(dicti.keys()))): # assigning value as key if found if ele in list(dicti.keys()): ele = dicti[ele] return ele# initializing dictionarytest_dict = {3: 4, 5: 6, 4: 8, 6: 9, 8: 10}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))res = dict()# iterating for each keyfor key, val in list(test_dict.items()): test_dict.pop(key) res[key] = find_depth(val, test_dict)# printing resultprint("The reassigned dictionary : " + str(res)) |
Output:
The original dictionary is : {3: 4, 5: 6, 4: 8, 6: 9, 8: 10}
The reassigned dictionary : {3: 10, 5: 9, 4: 10, 6: 9, 8: 10}
Method 2: Using loops
Loop is used to iterate over the keys and values of the dictionary and recursively calling a function to find the final value based on the path relation:
Approach:
- Define a function named find_final_value that takes in key and test_dict as arguments.
- Check if the key is not present in test_dict, if so, return the key itself as it is the final value.
- If the key is present in the test_dict, call the find_final_value function recursively by passing the value of the key in the test_dict as the new key and the test_dict as it is.
- Repeat step 2 and 3 until the final value is found.
- Initialize a dictionary test_dict with the given values.
- Iterate through each key in test_dict using a loop.
- Call the find_final_value function with the value of the current key in test_dict and the test_dict itself as arguments.
- Update the value of the current key in test_dict with the final value obtained in step 7.
- Print the updated test_dict.
Python3
def find_final_value(key, test_dict): if key not in test_dict: return key else: return find_final_value(test_dict[key], test_dict)# Input list test_dict = {3: 4, 5: 6, 4: 8, 6: 9, 8: 10}for key in test_dict: value = find_final_value(test_dict[key], test_dict) test_dict[key] = value# Printing result print(test_dict) |
{3: 10, 5: 9, 4: 10, 6: 9, 8: 10}
Time Complexity: O(n^2)
Auxiliary Space: O(n)
Method 3: Using dictionary comprehension
Python3
# Step 1: Define the function to find the final valuedef find_final_value(key, test_dict): while key in test_dict: key = test_dict[key] return key# Step 2: Define the dictionarytest_dict = {3: 4, 5: 6, 4: 8, 6: 9, 8: 10}# Step 3: Use dictionary comprehension to update the dictionary in one linetest_dict = {key: find_final_value(value, test_dict) for key, value in test_dict.items()}# Step 4: Print the updated dictionaryprint(test_dict) |
{3: 10, 5: 9, 4: 10, 6: 9, 8: 10}
Time complexity: O(n^2), where n is the number of keys in the dictionary.
Auxiliary space: O(n) to store the updated key-value pairs in a new dictionary.
