Sometimes, while working with data, we can have a problem in which we are provided with sample data of key and value list and we require to construct actual data as all possible combination of keys and value list of similar size. Lets discuss certain ways in which this task can be performed.
Method #1 : Using loop + set() The combination of above functionalities can be employed to solve this problem. In this, we initially extract all items flattened in list of sets. Then we construct each dictionary using set subtraction.
Python3
# Python3 code to demonstrate working of # All possible items combination dictionary# Using loop + set()# initializing Dictionarytest_dict = {'gfg' : [1, 3], 'is' : [5, 6], 'best' : [4, 7]}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# All possible items combination dictionary# Using loop + set()temp = [set([key]) | set(value) for key, value in test_dict.items() ]res = {}for sub in temp: for key in sub: res[key] = list(sub - set([key]))# printing result print("The all possible items dictionary : " + str(res)) |
The original dictionary is : {‘is’: [5, 6], ‘gfg’: [1, 3], ‘best’: [4, 7]} The all possible items dictionary : {1: [3, ‘gfg’], 3: [1, ‘gfg’], 4: [‘best’, 7], 5: [‘is’, 6], 6: [‘is’, 5], 7: [4, ‘best’], ‘best’: [4, 7], ‘is’: [5, 6], ‘gfg’: [1, 3]}
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 #2 : Using remove() + loop + update() This is yet another way in which this task can be performed. In this, we perform the task of removal of values already present using remove() and construct new dictionary items.
Python3
# Python3 code to demonstrate working of # All possible items combination dictionary# Using remove() + loop + update()# initializing Dictionarytest_dict = {'gfg' : [1, 3], 'is' : [5, 6], 'best' : [4, 7]}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# All possible items combination dictionary# Using remove() + loop + update()res = {}for key, val in test_dict.items(): for ele in val: temp = val[:] temp.remove(ele) res.update({ele: [key] + temp})test_dict.update(res)# printing result print("The all possible items dictionary : " + str(test_dict)) |
The original dictionary is : {‘is’: [5, 6], ‘gfg’: [1, 3], ‘best’: [4, 7]} The all possible items dictionary : {1: [3, ‘gfg’], 3: [1, ‘gfg’], 4: [‘best’, 7], 5: [‘is’, 6], 6: [‘is’, 5], 7: [4, ‘best’], ‘best’: [4, 7], ‘is’: [5, 6], ‘gfg’: [1, 3]}
Using bit manipulation:
Approach:
This function takes a dictionary and returns a list of all possible combinations of items in the dictionary.
Define a function named all_combinations that takes a dictionary dct as input.
Initialize an empty list result to store the result.
Calculate the length of the dictionary using n = len(dct).
Loop through all possible binary numbers with n digits using for i in range(2**n):. The 2**n generates all possible combinations of n bits, which is equivalent to the number of possible subsets of a set with n elements.
For each binary number i, initialize an empty dictionary named comb to store the selected key-value pairs.
Loop through the dictionary items using for j, (key, value) in enumerate(dct.items()):.
Check if the j-th bit of i is set to 1 using if i & (1 << j):. If it is, then include the key-value pair in comb.
Append the dictionary comb to the result list.
Return the result list.
Create a test dictionary original_dict.
Call the all_combinations function with original_dict as input and assign the result to a variable named result_dict.
Print the original dictionary and the resulting list of dictionaries.
Python3
def all_combinations(dct): result = [] n = len(dct) for i in range(2**n): comb = {} for j, (key, value) in enumerate(dct.items()): if i & (1 << j): comb[key] = value result.append(comb) return resultoriginal_dict = {'is': [5, 6], 'gfg': [1, 3], 'best': [4, 7]}result_dict = all_combinations(original_dict)print('Original dictionary:', original_dict)print('All possible items dictionary:', result_dict) |
Original dictionary: {'is': [5, 6], 'gfg': [1, 3], 'best': [4, 7]}
All possible items dictionary: [{}, {'is': [5, 6]}, {'gfg': [1, 3]}, {'is': [5, 6], 'gfg': [1, 3]}, {'best': [4, 7]}, {'is': [5, 6], 'best': [4, 7]}, {'gfg': [1, 3], 'best': [4, 7]}, {'is': [5, 6], 'gfg': [1, 3], 'best': [4, 7]}]
The time complexity of this approach is O(n * 2^n), where n is the number of items in the dictionary.
The space complexity is also O(n * 2^n), as the entire list of combinations needs to be stored in memory.
