Sometimes, while working with Python dictionaries, we can have problem in which we need to check if values of dictionaries don’t form a loop when they are mapped through key of other dictionaries. This kind of problem can have applications in many domains including competitive programming and brute force.
Input : test_dict1 = {9 : [1, 5], 8 : [1, 4], 10 : [4, 2]} test_dict2 = {2 : [1, 8]} Output : True Input : test_dict1 = {15 : [1, 5]} test_dict2 = {2 : [1, 10]} Output : False
Method #1 : Using loop
This is brute way in which this task can be performed. In this, we iterate for all the values of particular dictionary’s keys’ and map with values of similar keys in dictionary keys.
Python3
# Python3 code to demonstrate working of # Detect loop in Dictionaries# Using loop# initializing dictionariestest_dict1 = {7 : [1, 2], 8 : [1, 4], 9 : [4, 2]} test_dict2 = {2 : [1, 7], 10 : [1, 6], 11 : [24, 20]} # printing original dictionariesprint("The original dictionary 1 is : " + str(test_dict1))print("The original dictionary 2 is : " + str(test_dict2))# Detect loop in Dictionaries# Using loopres = Falsefor idx1 in test_dict1.values(): temp1 = (idx for idx in idx1 if idx in test_dict2) for idx in temp1: for idx2 in test_dict2[idx]: if idx2 in test_dict1: res = True# printing result print("Does dictionaries contain loop : " + str(res)) |
The original dictionary 1 is : {8: [1, 4], 9: [4, 2], 7: [1, 2]}
The original dictionary 2 is : {2: [1, 7], 11: [24, 20], 10: [1, 6]}
Does dictionaries contain loop : True
Method #2 : Using any() + loop
This is shorthand to solve this problem. In this, we reduce inner loop by inculcating any() and return True if any loop is present.
Python3
# Python3 code to demonstrate working of # Detect loop in Dictionaries# Using any() + loop# initializing dictionariestest_dict1 = {7 : [1, 2], 8 : [1, 4], 9 : [4, 2]} test_dict2 = {2 : [1, 7], 10 : [1, 6], 11 : [24, 20]} # printing original dictionariesprint("The original dictionary 1 is : " + str(test_dict1))print("The original dictionary 2 is : " + str(test_dict2))# Detect loop in Dictionaries# Using any() + loopres = Falsefor key, val in test_dict1.items(): if any([vl in test_dict2 and key in test_dict2[vl] for vl in val]): res = True# printing result print("Does dictionaries contain loop : " + str(res)) |
The original dictionary 1 is : {8: [1, 4], 9: [4, 2], 7: [1, 2]}
The original dictionary 2 is : {2: [1, 7], 11: [24, 20], 10: [1, 6]}
Does dictionaries contain loop : True
Method #3: Using the set intersection + loop: In this, we can use a for loop to iterate through the values of both dictionaries and use the set operation to find any common elements
Step-by-step algorithm :
- Initialize the dictionaries test_dict1 and test_dict2 with key-value pairs.
- Print the original dictionaries.
- Set the result variable to False.
- Use a nested for loop to iterate through the values of test_dict1 and test_dict2.
- Use the set operation to find if there are any common elements between the values.
- If there are any common elements, set the result variable to True and break the loop.
- Print the result.
Python3
# initializing dictionariestest_dict1 = {7 : [1, 2], 8 : [1, 4], 9 : [4, 2]} test_dict2 = {2 : [1, 7], 10 : [1, 6], 11 : [24, 20]} # printing original dictionariesprint("The original dictionary 1 is : " + str(test_dict1))print("The original dictionary 2 is : " + str(test_dict2))# Detect loop in Dictionaries# Using set and for loopres = Falsefor val1 in test_dict1.values(): for val2 in test_dict2.values(): if set(val1).intersection(set(val2)): res = True break if res: break# printing result print("Does dictionaries contain loop : " + str(res)) |
The original dictionary 1 is : {7: [1, 2], 8: [1, 4], 9: [4, 2]}
The original dictionary 2 is : {2: [1, 7], 10: [1, 6], 11: [24, 20]}
Does dictionaries contain loop : True
Time Complexity: O(n*n), where n is the size of the largest dictionary.
Auxiliary Space: O(k), where k is the number of distinct values in both dictionaries
