Python – Group similar elements into Matrix

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.

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:

1. Import the Counter() function from the collections module.
2. Initialize the input list.
3. Use the Counter() function to count the frequency of each element in the list.
4. 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.
5. Print the resulting list of sublists.

Below is the implementation of the above approach:

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.

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.

1. This code first initializes an empty matrix res. It then iterates through the original list test_list and for each element i.
2. It checks if there is already a sublist in ‘res’ that contains ‘i’. 
3. If there is, it appends ‘i’ to that sublist. If not, it creates a new sublist containing only i and appends it to res. 
4. In the end, res contains the desired matrix after grouping.

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:

1. Initialize an empty dictionary group_dict.
2. Iterate through the elements of the input list test_list.
3. For each element, check if it is already a key in the group_dict.
4. If it is not a key, add it as a key with a value of a list containing the element.
5. If it is already a key, append the element to the corresponding list.
6. Convert the dictionary to a list of lists to get the desired matrix form.
7. Print the resulting matrix.

Below is the implementation of the above approach:

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:

1. Initialize an empty list to store the grouped elements.
2. Use the set() function to get unique elements of the input list.
3. Loop through each unique element.
4. Use list comprehension to create a new list of lists with all occurrences of each unique element.
5. Append the new list to the empty list initialized in step 1.
6. Return the list of lists.

Below is the implementation of the above approach:

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

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

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)