Python – Group Similar items to Dictionary Values List
Given a list of elements, perform grouping of similar elements, as different key-value lists in a dictionary.
Input : test_list = [4, 6, 6, 4, 2, 2, 4, 8, 5, 8]
Output : {4: [4, 4, 4], 6: [6, 6], 2: [2, 2], 8: [8, 8], 5: [5]}
Explanation : Similar items grouped together on occurrences.Input : test_list = [7, 7, 7, 7]
Output : {7 : [7, 7, 7, 7]}
Explanation : Similar items grouped together on occurrences.
Method #1 : Using defaultdict() + loop
This is one of the ways in which this task can be performed. In this, we construct a defaultdict() with a default list and keep appending similar values into a similar list.
Step-by-step approach:
- Import the defaultdict class from the collections module.
- Create a list called test_list containing several integers.
- Print the original list.
- Create an empty dictionary using the defaultdict class and assign it to a variable called res.
- Loop through each element in the test_list.
- Append the current element to the list in the res dictionary corresponding to its value.
- Print the resulting dictionary, which contains groups of similar items as values.
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate working of # Group Similar items to Dictionary Values List # Using defaultdict + loop from collections import defaultdict # initializing list test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] # printing original list print ( "The original list : " + str (test_list)) # using defaultdict for default list res = defaultdict( list ) for ele in test_list: # appending Similar values res[ele].append(ele) # printing result print ( "Similar grouped dictionary : " + str ( dict (res))) |
The original list : [4, 6, 6, 4, 2, 2, 4, 4, 8, 5, 8] Similar grouped dictionary : {4: [4, 4, 4, 4], 6: [6, 6], 2: [2, 2], 8: [8, 8], 5: [5]}
Time Complexity: O(N)
Auxiliary Space: O(N)
Method #2 : Using dictionary comprehension + Counter()
This is yet another way in which this task can be performed. In this, we extract frequency using Counter() and then repeat occurrences using multiplication.
Python3
# Python3 code to demonstrate working of # Group Similar items to Dictionary Values List # Using dictionary comprehension + Counter() from collections import Counter # initializing list test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] # printing original list print ( "The original list : " + str (test_list)) # using * operator to perform multiplication res = {key : [key] * val for key, val in Counter(test_list).items()} # printing result print ( "Similar grouped dictionary : " + str (res)) |
The original list : [4, 6, 6, 4, 2, 2, 4, 4, 8, 5, 8] Similar grouped dictionary : {4: [4, 4, 4, 4], 6: [6, 6], 2: [2, 2], 8: [8, 8], 5: [5]}
Time Complexity: O(n) where n is the number of elements in the list
Auxiliary Space: O(n), where n is the number of elements in the list
Method #3: Using set() and list comprehension
In this method, we first use the set() function to get the unique elements in the list. We then create a dictionary with empty lists as values using a dictionary comprehension. Finally, we use a list comprehension to iterate through the input list and append each item to the corresponding list in the dictionary.
Python3
# initializing list test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] # printing original list print ( "The original list : " + str (test_list)) # using set() to get unique elements in list unique_items = set (test_list) # creating dictionary with empty lists as values res = {key: [] for key in unique_items} # using list comprehension to group similar items [res[item].append(item) for item in test_list] # printing result print ( "Similar grouped dictionary : " + str (res)) |
The original list : [4, 6, 6, 4, 2, 2, 4, 4, 8, 5, 8] Similar grouped dictionary : {2: [2, 2], 4: [4, 4, 4, 4], 5: [5], 6: [6, 6], 8: [8, 8]}
Time complexity: O(n) because we are using a set() to get the unique elements in the list, which takes O(n) time. Creating the dictionary with empty lists as values using dictionary comprehension takes O(m) time, where m is the number of unique elements in the list.
Auxiliary space: O(m + n) because we are creating a dictionary with m keys and empty lists as values, and also creating a set() with n elements.
Method 4: Using the groupby function from the itertools module.
Step-by-step approach:
- Import the itertools module.
- Sort the original list.
- Use the groupby function to group similar items.
- Create a dictionary with the groups as keys and the items in the group as values.
- Print the resulting dictionary.
Below is the implementation of the above approach:
Python3
# Step 1 import itertools # initializing list test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] # Step 2 test_list.sort() # Step 3 groups = itertools.groupby(test_list) # Step 4 res = {k: list (v) for k, v in groups} # Step 5 print ( "Similar grouped dictionary : " + str (res)) |
Similar grouped dictionary : {2: [2, 2], 4: [4, 4, 4, 4], 5: [5], 6: [6, 6], 8: [8, 8]}
Time complexity: O(n log n) due to the sorting operation.
Auxiliary space: O(n) for storing the dictionary.
Method 5: Using the itertools.zip_longest function
- Import the itertools module.
- Sort the given list test_list.
- Use the zip_longest() function from the itertools module to group the consecutive identical elements in the sorted list into tuples.
- Convert the tuples into lists.
- Create a dictionary with the lists as values and the first element of each tuple as the key.
- Print the resulting dictionary.
Python3
import itertools test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] test_list.sort() grouped_lists = [ list (g) for k, g in itertools.groupby(test_list)] res_dict = {lst[ 0 ]: lst for lst in grouped_lists} print ( "Similar grouped dictionary: " , res_dict) |
Similar grouped dictionary: {2: [2, 2], 4: [4, 4, 4, 4], 5: [5], 6: [6, 6], 8: [8, 8]}
Time complexity: O(N log(N)) due to the sorting of the list.
Auxiliary space: O(N) for the resulting dictionary.
Method 6: Using a while loop and a temporary list
Step-by-step approach:
- Sort the given list in ascending order
- Initialize an empty dictionary ‘res’
- Initialize an empty list ‘temp’
- Initialize a variable ‘prev’ with None
- Use a while loop to iterate through the sorted list
- If the current element is equal to ‘prev’ or if ‘prev’ is None, append the current element to ‘temp’
- If the current element is not equal to ‘prev’, add the current ‘temp’ list to the ‘res’ dictionary with ‘prev’ as key
- Update the value of ‘prev’ to the current element
- After the loop, add the last ‘temp’ list to the ‘res’ dictionary with the last element of the list as key
- Print the ‘res’ dictionary
Below is the implementation of the above approach:
Python3
test_list = [ 4 , 6 , 6 , 4 , 2 , 2 , 4 , 4 , 8 , 5 , 8 ] test_list.sort() res = {} temp = [] prev = None while test_list: curr = test_list.pop( 0 ) if curr = = prev or prev is None : temp.append(curr) else : res[prev] = temp temp = [curr] prev = curr res[prev] = temp print ( "Similar grouped dictionary : " + str (res)) |
Similar grouped dictionary : {2: [2, 2], 4: [4, 4, 4, 4], 5: [5], 6: [6, 6], 8: [8, 8]}
Time Complexity: O(nlogn) for sorting the list and O(n) for iterating through the list
Auxiliary Space: O(n)