Sometimes, while working with Python Matrix, we can have a problem in which we need to perform grouping of all the elements with are the same. This kind of problem can have applications in data domains. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [1, 3, 4, 4, 2, 3]
Output : [[1], [2], [3, 3], [4, 4]]
Input : test_list = [1, 3, 4, 2]
Output : [[1], [2], [3], [4]]
Method #1: Using list comprehension + groupby()
The combination of the above functions provides a possible solution to this problem. In this, we perform the task of grouping using groupby() and list comprehension assists in iteration.
Python3
from itertools import groupby
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
print("The original list : " + str(test_list))
res = [list(val) for key, val in groupby(sorted(test_list))]
print("Matrix after grouping : " + str(res))
|
Output :
The original list : [1, 3, 5, 1, 3, 2, 5, 4, 2]
Matrix after grouping : [[1, 1], [2, 2], [3, 3], [4], [5, 5]]
Time complexity: O(n log n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list. This is because the result list ‘res’ will have at most n elements, where each element is a list containing the grouped similar elements.
Method #2: Using list comprehension + Counter()
This is yet another approach to this problem. In this, we get the values along with its frequency using Counter() and then employ list comprehension to multiply each element with frequency to get duplicates
Approach:
- Import the Counter() function from the collections module.
- Initialize the input list.
- Use the Counter() function to count the frequency of each element in the list.
- Use a list comprehension to create a list of sublists, where each sublist contains the key element repeated by the value count number of times.
- Print the resulting list of sublists.
Below is the implementation of the above approach:
Python3
from collections import Counter
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
print("The original list : " + str(test_list))
temp = Counter(test_list)
res = [[key] * val for key, val in temp.items()]
print("Matrix after grouping : " + str(res))
|
Output :
The original list : [1, 3, 5, 1, 3, 2, 5, 4, 2]
Matrix after grouping : [[1, 1], [2, 2], [3, 3], [4], [5, 5]]
Time complexity: O(n log n), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
Method #3: Using defaultdict
defaultdict is a subclass of the built-in dict class and provides a default value for a nonexistent key. Use a defaultdict to group similar elements into a list.
Python3
from collections import defaultdict
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
print("The original list : " + str(test_list))
d = defaultdict(list)
for element in test_list:
d[element].append(element)
res = list(d.values())
print("Matrix after grouping : " + str(res))
|
Output
The original list : [1, 3, 5, 1, 3, 2, 5, 4, 2]
Matrix after grouping : [[1, 1], [3, 3], [5, 5], [2, 2], [4]]
Time Complexity: O(n), where n is the length of the input list,
Auxiliary Space: O(n), as we are using a defaultdict to store the groups of similar elements.
Method #4: Using nested loops to iterate through the list and build the matrix.
- This code first initializes an empty matrix res. It then iterates through the original list test_list and for each element i.
- It checks if there is already a sublist in ‘res’ that contains ‘i’.
- If there is, it appends ‘i’ to that sublist. If not, it creates a new sublist containing only i and appends it to res.
- In the end, res contains the desired matrix after grouping.
Python3
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
res = []
for i in test_list:
found = False
for j in range(len(res)):
if i in res[j]:
res[j].append(i)
found = True
break
if not found:
res.append([i])
print("Matrix after grouping : " + str(res))
|
Output
Matrix after grouping : [[1, 1], [3, 3], [5, 5], [2, 2], [4]]
Time complexity: O(n^2), where n is the length of test_list.
Auxiliary space: O(n), where n is the length of test_list.
Method 5: Using dictionary to group the elements of the list.
Approach:
- Initialize an empty dictionary group_dict.
- Iterate through the elements of the input list test_list.
- For each element, check if it is already a key in the group_dict.
- If it is not a key, add it as a key with a value of a list containing the element.
- If it is already a key, append the element to the corresponding list.
- Convert the dictionary to a list of lists to get the desired matrix form.
- Print the resulting matrix.
Below is the implementation of the above approach:
Python3
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
group_dict = {}
for element in test_list:
if element not in group_dict:
group_dict[element] = [element]
else:
group_dict[element].append(element)
res = list(group_dict.values())
print("Matrix after grouping: " + str(res))
|
Output
Matrix after grouping: [[1, 1], [3, 3], [5, 5], [2, 2], [4]]
Time complexity: O(n)
Auxiliary space: O(n) for the dictionary.
Method 6: Use the set() function
Here we will get unique elements of the list, and then use list comprehension to create a new list of lists with all occurrences of each unique element.
Approach:
- Initialize an empty list to store the grouped elements.
- Use the set() function to get unique elements of the input list.
- Loop through each unique element.
- Use list comprehension to create a new list of lists with all occurrences of each unique element.
- Append the new list to the empty list initialized in step 1.
- Return the list of lists.
Below is the implementation of the above approach:
Python3
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
grouped = []
unique = set(test_list)
for element in unique:
sublist = [x for x in test_list if x == element]
grouped.append(sublist)
print("Matrix after grouping: " + str(grouped))
|
Output
Matrix after grouping: [[1, 1], [2, 2], [3, 3], [4], [5, 5]]
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
Method 6: Use the set() without using list comprehension
Python3
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
unique = set(test_list)
grouped = [[] for _ in range(len(unique))]
for i, element in enumerate(unique):
for x in test_list:
if x == element:
grouped[i].append(x)
print("Matrix after grouping: " + str(grouped))
|
Output
Matrix after grouping: [[1, 1], [2, 2], [3, 3], [4], [5, 5]]
Time complexity: O(n^2), where n is the length of the input list.
Auxiliary space: O(n), where n is the length of the input list.
Method 7: Using NumPy
- Import the NumPy library
- Use np.unique() to get unique elements of the list
- Use np.zeros() to create a matrix of zeros with the shape (len(unique), max(counts))
- Use nested loops to iterate through the unique elements and their counts, and fill in the matrix with the Step 5: Print the matrix
Python3
import numpy as np
test_list = [1, 3, 5, 1, 3, 2, 5, 4, 2]
unique, counts = np.unique(test_list, return_counts=True)
matrix = np.zeros((len(unique), np.max(counts)), dtype=int)
for i, element in enumerate(unique):
for j in range(counts[i]):
matrix[i,j] = element
result = []
for row in matrix:
result.append([x for x in row if x != 0])
print("Matrix after grouping: " + str(result))
|
Output:
Matrix after grouping: [[1, 1], [2, 2], [3, 3], [4], [5, 5]]
Time complexity: O(n log n) (worst case for np.unique() to sort the array)
Auxiliary space: O(n * k) (for the matrix, where k is the maximum count of an element)
Please Login to comment...