Given a dictionary with string keys and sets as values the task is to write a python program to concatenate keys all of which have similar values order irrespective.
Input : test_dict = {‘gfg’ : {5, 4, 3}, ‘is’ : {4, 3, 5}, ‘best’ : {1, 4, 3}, ‘for’ : {1, 3, 4}, ‘neveropen’ : {1, 2, 3}}
Output : {‘gfg-is’: frozenset({3, 4, 5}), ‘best-for’: frozenset({1, 3, 4}), ‘neveropen’: frozenset({1, 2, 3})}
Explanation : Similar set keys are concatenated, {5, 4, 3} == {4, 3, 5}, hence gfg-is are concatenated.
Input : test_dict = {‘gfg’ : {5, 4, 3}, ‘is’ : {4, 3, 5}, ‘neveropen’ : {1, 2, 3}}
Output : {‘gfg-is’: frozenset({3, 4, 5}), ‘neveropen’: frozenset({1, 2, 3})}
Explanation : Similar set keys are concatenated, {5, 4, 3} == {4, 3, 5}, hence gfg-is are concatenated.
Method #1 : Using defaultdict() + join()
In this, we perform the task of hashing each set and appending corresponding keys using defaultdict(). The next step is to join all the hashed keys to similar set values.
Python3
# Python3 code to demonstrate working of# Concatenate similar set keys in Dictionary# Using defaultdict() + join()from collections import defaultdict# initializing dictionarytest_dict = {'gfg': {5, 4, 3}, 'is': {4, 3, 5}, 'best': { 1, 4, 3}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))hash_vals = defaultdict(list)for key, val in test_dict.items(): # values are hashed using frozenset hash_vals[frozenset(val)].append(key)# perform joiningres = {'-'.join(keys): vals for (vals, keys) in hash_vals.items()}# printing resultprint("The concatenated keys : " + str(res)) |
Output:
The original dictionary is : {‘gfg’: {3, 4, 5}, ‘is’: {3, 4, 5}, ‘best’: {1, 3, 4}, ‘for’: {1, 3, 4}, ‘neveropen’: {1, 2, 3}}
The concatenated keys : {‘gfg-is’: frozenset({3, 4, 5}), ‘best-for’: frozenset({1, 3, 4}), ‘neveropen’: frozenset({1, 2, 3})}
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using groupby() + join() + dictionary comprehension
In this, we perform tasks of grouping like elements using groupby(). After that joining alike valued keys is done using join().
Python3
# Python3 code to demonstrate working of# Concatenate similar set keys in Dictionary# Using groupby() + join() + dictionary comprehensionfrom itertools import groupby# initializing dictionarytest_dict = {'gfg': {5, 4, 3}, 'is': {4, 3, 5}, 'best': {1, 4, 3}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# elements grouped using groupby()# dictionary comprehension provides shorthand to perform groupingres = {'-'.join(val): key for key, val in groupby( sorted(test_dict, key=test_dict.get), key=lambda sub: test_dict[sub])}# printing resultprint("The concatenated keys : " + str(res)) |
Output:
The original dictionary is : {‘gfg’: {3, 4, 5}, ‘is’: {3, 4, 5}, ‘best’: {1, 3, 4}, ‘for’: {1, 3, 4}, ‘neveropen’: {1, 2, 3}}
The concatenated keys : {‘gfg-is’: {3, 4, 5}, ‘best-for’: {1, 3, 4}, ‘neveropen’: {1, 2, 3}}
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #3: Using normal dictionary iteration and list comprehension
we will iterate through the original dictionary and create a new dictionary using list comprehension to concatenate the keys with the same values.
Step-by-step approach:
- Create an empty dictionary to store the concatenated keys and values.
- Create an empty set to keep track of the processed keys.
- Loop through each key-value pair in the dictionary.
- Check if the current key has already been processed. If it has, skip it and move to the next key.
- Create a set to store the keys that have the same set of values as the current key. Add the current key to this set.
- Loop through the remaining keys in the dictionary.
- Check if the current key has already been processed or is the same as the previous key. If it has, skip it and move to the next key.
- Check if the values of the current key and the previous key are the same. If they are, add the current key to the set of similar keys.
- Concatenate the keys in the set of similar keys and store the result in the dictionary, using the sorted keys as the concatenated key.
- Add all the keys in the set of similar keys and the current key to the set of processed keys.
- Print the concatenated keys and values in the resulting dictionary.
Python3
# Python3 code to demonstrate working of# Concatenate similar set keys in Dictionary# Using loop to group keys# initializing dictionarytest_dict = {'gfg': {5, 4, 3}, 'is': {4, 3, 5}, 'best': { 1, 4, 3}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# create an empty dictionary to store the resultres = {}# create an empty set to store the processed keysprocessed_keys = set()# iterate over the dictionary's key-value pairsfor key1, val1 in test_dict.items(): # check if the current key has already been processed if key1 not in processed_keys: # create a set to store the keys that have the same value as the current key similar_keys = {key1} # iterate over the remaining key-value pairs for key2, val2 in test_dict.items(): # check if the current key has already been processed or is the same as the previous key if key2 not in processed_keys and key2 != key1: # check if the values are the same if val1 == val2: # add the key to the set of similar keys similar_keys.add(key2) # add the key to the set of processed keys processed_keys.add(key2) # concatenate the keys and store the result in the dictionary res['-'.join(sorted(similar_keys))] = val1 # add the keys to the set of processed keys processed_keys.add(key1)# printing resultprint("The concatenated keys : " + str(res)) |
The original dictionary is : {'gfg': {3, 4, 5}, 'is': {3, 4, 5}, 'best': {1, 3, 4}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}
The concatenated keys : {'gfg-is': {3, 4, 5}, 'best-for': {1, 3, 4}, 'neveropen': {1, 2, 3}}
Time complexity: O(n^2), where n is the number of key-value pairs in the dictionary. This is because we need to compare each pair of keys with each other.
Auxiliary space: O(n), where n is the number of key-value pairs in the dictionary. This is because we need to create a set to store the processed keys, which can have up to n elements.
Method #4: Using the heapq module:
Algorithm:
- Create an empty dictionary res to store the final result.
- Convert the original dictionary test_dict into a list of tuples (key, value) and then create another list heap of tuples where the second element is the key and the first element is the negative of the length of the corresponding value set.
- Heapify the list heap.
- Repeat the following steps until heap is not empty:
a. Pop an element from the heap as (_, key, val).
b. Check if any remaining keys have the same value as this key, if yes, append them to the current key by joining with ‘-‘.
c. Add the current key and val pair to the res dictionary. - Print the res dictionary.
Python3
# Python3 code to demonstrate working of# Concatenate similar set keys in Dictionary# Using heapq() + join() + dictionary comprehensionimport heapq# initializing dictionarytest_dict = {'gfg': {5, 4, 3}, 'is': {4, 3, 5}, 'best': {1, 4, 3}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}# printing original dictionaryprint("The original dictionary is : " + str(test_dict))# creating a list of (set, key) pairsheap = [(-len(val), key, val) for key, val in test_dict.items()]# heapifying the listheapq.heapify(heap)res = {}while heap: _, key, val = heapq.heappop(heap) # check if any remaining keys have the same values as this key while heap and heap[0][2] == val: _, next_key, _ = heapq.heappop(heap) key += '-' + next_key res[key] = val# printing resultprint("The concatenated keys : " + str(res))#This code is contributed by Jyothi pinjala. |
The original dictionary is : {'gfg': {3, 4, 5}, 'is': {3, 4, 5}, 'best': {1, 3, 4}, 'for': {1, 3, 4}, 'neveropen': {1, 2, 3}}
The concatenated keys : {'best-for': {1, 3, 4}, 'neveropen': {1, 2, 3}, 'gfg-is': {3, 4, 5}}
Time Complexity: The time complexity of the solution is O(n log n) where n is the number of elements in the input dictionary. This is because heapifying the list of tuples takes O(n log n) time and popping elements from the heap takes O(log n) time for each element. The while loop inside the outer loop may execute multiple times, but the total number of iterations across all iterations is still bounded by n.
Auxiliary Space: The space complexity of the solution is O(n) where n is the number of elements in the input dictionary. This is because we create a heap of n tuples, each containing the key and the negative of the length of the value set. The dictionary res also has n entries.
