Sometimes, while working with Python dictionaries, we can have a problem in which we need to get all the possible pair combinations of dictionary pairs. This kind of application can occur in the data science domain. Let’s discuss certain ways in which this task can be performed.
Method #1: Using list comprehension + enumerate() In this method, we just iterate the dictionary through list comprehension and construct the pairs of keys and insert in new list. The enumerate function is used to bind the key elements together by accessing the indices.
Python3
# Python3 code to demonstrate working of# Dictionary key combinations# Using list comprehension + enumerate()# Initializing dicttest_dict = {'gfg' : 1, 'is' : 2, 'the' : 3, 'best' : 4}# printing original dictprint("The original dict is : " + str(test_dict))# Dictionary key combinations# Using list comprehension + enumerate()test_dict = list(test_dict)res = [(x, y) for idx, x in enumerate(test_dict) for y in test_dict[idx + 1: ]] # printing resultprint("The dictionary key pair list is : " + str(res)) |
The original dict is : {'is': 2, 'the': 3, 'best': 4, 'gfg': 1}
The dictionary key pair list is : [('is', 'the'), ('is', 'best'), ('is', 'gfg'), ('the', 'best'), ('the', 'gfg'), ('best', 'gfg')]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using itertools.combinations() This task can be performed using the functionality of combinations(), which internally takes just the keys to form the element pairs.
Python3
# Python3 code to demonstrate working of# Dictionary key combinations# Using itertools.combinations()import itertools# Initializing dicttest_dict = {'gfg' : 1, 'is' : 2, 'the' : 3, 'best' : 4}# printing original dictprint("The original dict is : " + str(test_dict))# Dictionary key combinations# Using itertools.combinations()res = list(itertools.combinations(test_dict, 2))# printing resultprint("The dictionary key pair list is : " + str(res)) |
The original dict is : {'is': 2, 'the': 3, 'best': 4, 'gfg': 1}
The dictionary key pair list is : [('is', 'the'), ('is', 'best'), ('is', 'gfg'), ('the', 'best'), ('the', 'gfg'), ('best', 'gfg')]
Time complexity: O(n^2), where n is the length of the input dictionary. This is because the program uses the itertools.combinations() method to generate all possible pairs of keys in the dictionary. The itertools.combinations() method generates n choose 2 (i.e., n(n-1)/2) pairs, which takes O(n^2) time.
Auxiliary space: O(n^2), where n is the length of the input dictionary.
Method 3: Using Recursion:
Generate all possible key pairs from a given dictionary using recursion.
This approach defines a recursive function key_pairs() that generates all possible key pairs by iterating through the dictionary keys and calling the function recursively on the remaining keys. The function returns a set of unique key pairs. Since the function iterates over all the keys in the dictionary, it is not as efficient as the other approaches, especially for large dictionaries.
Python3
# Initializing dicttest_dict = {'gfg': 1, 'is': 2, 'the': 3, 'best': 4}# printing original dictprint("The original dict is : " + str(test_dict))# Dictionary key combinations using recursiondef key_pairs(d): if len(d) < 2: return set() k1 = next(iter(d)) return {(k1, k2) for k2 in d.keys() if k2 != k1}.union(key_pairs({k: v for k, v in d.items() if k != k1}))res = key_pairs(test_dict)# printing resultprint("The dictionary key pair set is : " + str(res)) |
The original dict is : {'gfg': 1, 'is': 2, 'the': 3, 'best': 4}
The dictionary key pair set is : {('gfg', 'the'), ('the', 'best'), ('is', 'the'), ('is', 'best'), ('gfg', 'best'), ('gfg', 'is')}
Time complexity: O(n^2), the recursion generates all possible key pairs, resulting in n(n-1)/2 pairs in the worst case, which is O(n^2).
Auxiliary space: O(n^2), the set of key pairs can contain up to n(n-1)/2 pairs in the worst case, resulting in O(n^2) space complexity. Additionally, the recursion call stack can grow up to n in the worst case, resulting in O(n) auxiliary space complexity.
Method 4 : using a nested loop over the keys.
step by step approach
- Initialize the dictionary
- Create an empty list to store the combinations of keys
- Loop over the keys of the dictionary using a for loop
- Inside the first loop, create another loop to iterate over the remaining keys
- Check if the current pair of keys is not the same
- Create a tuple with the current pair of keys and append it to the list of combinations
Python3
# Initializing dicttest_dict = {'gfg': 1, 'is': 2, 'the': 3, 'best': 4}# printing original dictprint("The original dict is : " + str(test_dict))# Dictionary key combinations using nested loopkey_combinations = []for key1 in test_dict.keys(): for key2 in test_dict.keys(): if key1 != key2: key_combinations.append((key1, key2))# printing resultprint("The dictionary key pair list is : " + str(key_combinations)) |
The original dict is : {'gfg': 1, 'is': 2, 'the': 3, 'best': 4}
The dictionary key pair list is : [('gfg', 'is'), ('gfg', 'the'), ('gfg', 'best'), ('is', 'gfg'), ('is', 'the'), ('is', 'best'), ('the', 'gfg'), ('the', 'is'), ('the', 'best'), ('best', 'gfg'), ('best', 'is'), ('best', 'the')]
The time complexity of this method is O(n^2) since we loop twice over the keys of the dictionary. \
The auxiliary space is O(n^2) since we store all combinations of keys in a list.
