Python – Key Value list pairings in Dictionary

Sometimes, while working with Python dictionaries, we can have problems in which we need to pair all the keys with all values to form a dictionary with all possible pairings. This can have application in many domains including day-day programming. Lets discuss certain ways in which this task can be performed.

Method #1: Using list comprehension This task can be performed using this method. In this we manually extract each key and then iterate with all the values of them to form new dictionary list. This has drawbacks of only available for certain keys. 

The time complexity of the given code is O(N^2), where N is the size of the largest list in the dictionary.

The auxiliary space complexity of the given code is also O(N^2), as the result list ‘res’ contains N^2 key-value pairs, where N is the size of the largest list in the dictionary.

Method #2: Using dict() + zip() + product() The combination of above methods can also be used to perform this task. In this, the formation of combinations is done using product(), and linking of values is done using zip(). 

Time Complexity: O(n*n), where n is the length of the list test_dict
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list

Method 3: Using a recursive approach 

Step-by-step approach:

1. Define a function called key_value_combinations that takes two arguments: keys and values. The keys argument is a list of keys, and the values argument is a list of lists, where each inner list represents the possible values for a key.
2. In the function, create an empty list called combinations.
3. Define a recursive function called generate_combinations that takes two arguments: current_combination and remaining_values. The current_combination argument is a dictionary that represents the key-value pairs generated so far, and the remaining_values argument is a list of lists, where each inner list represents the possible values for a key that has not been assigned a value yet.
4. In the generate_combinations function, if the remaining_values list is empty, append the current_combination dictionary to the combinations list and return.
5. Otherwise, pop the first list from the remaining_values list, and iterate over its elements. For each element, create a new dictionary by adding a key-value pair to the current_combination dictionary, where the key is the first key from the keys list, and the value is the current element from the popped list. Call the generate_combinations function recursively with the updated current_combination dictionary and the remaining values in the remaining_values list.
6. Call the generate_combinations function with an empty dictionary as the current_combination argument and the values list as the remaining_values argument.
7. Return the combinations list.

Below is the implementation of the above approach:

All key value paired List : [{'gfg': 10}, {'gfg': 11}, {'gfg': 7}, {'gfg': 10}, {'gfg': 11}, {'gfg': 7}]

Time complexity: O(n^m), where n is the maximum length of any value list, and m is the number of keys. 
Auxiliary space: O(n^m), as we need to store all possible combinations.

Method 4: Using itertools.product() with dictionary items()

Use the itertools.product() function along with the dictionary items() method to generate all possible combinations of key-value pairs.

Step-by-step approach:

• Get the items in the dictionary using the items() method and store them in a list.
• Use itertools.product() function to generate all possible combinations of values.
• Combine each combination with the corresponding keys using the zip() function and store them in a list.

Below is the implementation of the above approach:

All key value paired List : [{'gfg': 7, 'best': 10}, {'gfg': 7, 'best': 11}, {'gfg': 7, 'best': 7}, {'gfg': 8, 'best': 10}, {'gfg': 8, 'best': 11}, {'gfg': 8, 'best': 7}]

Time complexity: O(n^m), where n is the maximum number of values for a key, and m is the number of keys.
Auxiliary space: O(n^m), to store all the combinations.

Method 5: Using nested for loops and a temporary dictionary

Step-by-step approach:

Define the dictionary test_dict with the given key-value pairs.
Print the original dictionary using print().
Initialize an empty list res to store the final result.
Use nested for loops to iterate over the values of the keys ‘gfg’ and ‘best’ in the dictionary test_dict.
For each pair of values, create a temporary dictionary temp_dict with the key-value pairs.
Append the temporary dictionary to the list res.
Print the final result using print().

The original dictionary is : {'gfg': [7, 8], 'best': [10, 11, 7]}
All key value paired List : [{'gfg': 7, 'best': 10}, {'gfg': 7, 'best': 11}, {'gfg': 7, 'best': 7}, {'gfg': 8, 'best': 10}, {'gfg': 8, 'best': 11}, {'gfg': 8, 'best': 7}]

Time complexity: O(n^2), where n is the length of the longest list in the dictionary test_dict.
Auxiliary space: O(1), because the algorithm only uses a temporary dictionary and a list to store the final result, regardless of the size of the input.