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:

1. Import the defaultdict class from the collections module.
2. Create a list called test_list containing several integers.
3. Print the original list.
4. Create an empty dictionary using the defaultdict class and assign it to a variable called res.
5. Loop through each element in the test_list.
   1. Append the current element to the list in the res dictionary corresponding to its value.
6. Print the resulting dictionary, which contains groups of similar items as values.

Below is the implementation of the above approach:

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.

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.

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:

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

1. Import the itertools module.
2. Sort the given list test_list.
3. Use the zip_longest() function from the itertools module to group the consecutive identical elements in the sorted list into tuples.
4. Convert the tuples into lists.
5. Create a dictionary with the lists as values and the first element of each tuple as the key.
6. Print the resulting dictionary.

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:

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)

manjeet_04

Follow

Improve