Sometimes, while working with Python Matrix, we can have data arranged randomly and we can have a requirement in which we need to get the element position in sorted order of Matrix. Let’s discuss a certain way in which this task can be performed. Method : Using list comprehension + enumerate() + sort() + lambda The solution to problem can be achieved using the combination of above functions. In these, we need to first arrange element for index value tuple creation using enumerate() and list comprehension. Then, we employ sort function to perform custom sort using lambda function.
Code :
Python3
# Python3 code to demonstrate working of# Relative sorted order in Matrix# using list comprehension + enumerate() + sort() + lambda# initialize listtest_list = [[1, 3, 1], [4, 6], [7, 8, 10]]# printing original listprint("The original list is : " + str(test_list))# Relative sorted order in Matrix# using list comprehension + enumerate() + sort() + lambdares = [(i, j) for i, x in enumerate(test_list) for j, _ in enumerate(x)]res.sort(key = lambda f: test_list[f[0]][f[1]])# printing resultprint("Sorted order of Matrix elements : " + str(res)) |
The original list is : [[1, 3, 1], [4, 6], [7, 8, 10]]
Sorted order of Matrix elements : [(0, 0), (0, 2), (0, 1), (1, 0),
(1, 1), (2, 0), (2, 1), (2, 2)]
Time complexity: O(M^N) as the number of combinations generated is M choose N.
Auxiliary space: O(M^N) as the size of the resultant list is also M choose N.
Method #2: Using numpy and argsort
Step by step Algorithm:
- Initialize a 2D list matrix with some values and a list relative_order containing the desired order of the elements.
- Create a flattened numpy array flat_array from the matrix.
- Use a list comprehension to get the indices in relative_order for each element in flat_array, if it exists in relative_order, otherwise use the
- length of relative_order as the index.
- Use numpy.argsort() to get the indices that would sort the array in ascending order.
- Use numpy.unravel_index() to reshape the sorted indices into the shape of the original matrix.
- Print the result.
Python3
import numpy as np# define the original matrix and the relative order listmatrix = [[1, 3, 1], [4, 6], [7, 8, 10]]relative_order = [1, 3, 5, 7, 2, 4, 6, 8, 9, 10]# create a flattened numpy array from the matrixflat_array = np.array([elem for row in matrix for elem in row])# get the indices that would sort the array in ascending ordersorted_indices = np.argsort([np.where(np.array(relative_order) == elem)[0][0] if elem in relative_order else len(relative_order) for elem in flat_array])# reshape the sorted indices into the shape of the original matrixsorted_matrix = np.unravel_index(sorted_indices, np.shape(matrix))# print the resultprint("The original matrix is:", matrix)print("Sorted order of Matrix elements:", list(zip(sorted_matrix[0], sorted_matrix[1]))) |
The original list is :[[1, 3, 1], [4, 6], [7, 8, 10]] Sorted order of Matrix elements : [(0, 0), (0, 2), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2)]
Time Complexity: O(nlogn), where n is the number of elements in the matrix, due to the np.argsort() function used.
Space Complexity: O(n), as we are creating a flattened numpy array of the original matrix and also storing the sorted indices.
Method #3: Using itertools.product() and list comprehension
- Import the itertools module.
- Initialize the matrix as a list of lists.
- Print the original matrix.
- Use itertools.product() to generate pairs of row and column indices for each element in the matrix.
- Use a list comprehension to filter out invalid indices.
- Sort the resulting list of tuples based on the element values in the matrix.
- Print the sorted list of tuples.
Python3
import itertools# initialize listtest_list = [[1, 3, 1], [4, 6], [7, 8, 10]]# printing original listprint("The original list is : " + str(test_list))# Relative sorted order in Matrix# using itertools.product() and list comprehensionres = [(i, j) for i, j in itertools.product(range(len(test_list)), range(max(map(len, test_list)))) if j < len(test_list[i])]res.sort(key = lambda f: test_list[f[0]][f[1]])# printing resultprint("Sorted order of Matrix elements : " + str(res)) |
The original list is : [[1, 3, 1], [4, 6], [7, 8, 10]] Sorted order of Matrix elements : [(0, 0), (0, 2), (0, 1), (1, 0), (1, 1), (2, 0), (2, 1), (2, 2)]
Time complexity: O(n*log(n)), where n is the number of rows in the matrix
Space complexity: O(n), where n is the number of rows in the matrix.
