Python Program to sort rows of a matrix by custom element count

0 0 3 minutes read

Given Matrix, the following program shows how to sort rows of a matrix by the count of presence of numbers from a specified list.

Input : test_list = [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]], cus_list = [4, 5, 7]
Output : [[9, 8, 2], [6, 5], [7, 1], [4, 5, 1, 7]]
Explanation : 0 < 1 = 1 < 3 is order of custom elements count.
Input : test_list = [[4, 5, 1, 7], [6, 5], [7, 1]], cus_list = [4, 5, 7]
Output : [[6, 5], [7, 1], [4, 5, 1, 7]]
Explanation : 1 = 1 < 3 is order of custom elements count.

Method 1 : Using sort() and len()

In this, we perform in-place sort using sort(), and check for all elements and increase counter in cases of element presence from custom list, len() returns length to get count.

Python3

# sorting util.
def get_count(sub):
    return len([ele for ele in sub if ele in cus_list])
 
 
# initializing list
test_list = [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing custom list
cus_list = [4, 5, 7]
 
# performing inplace sort
test_list.sort(key=get_count)
 
# printing result
print("Sorted Matrix : " + str(test_list))

Output:

The original list is : [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
Sorted Matrix : [[9, 8, 2], [6, 5], [7, 1], [4, 5, 1, 7]]

Time Complexity: O(nlogn+mlogm)
Auxiliary Space: O(k)

Method 2 : Using sorted(), lambda and len()

Another way of solving this problem is to perform the task of sorting using sorted() and lambda function offers one statement logic without calling external function.

Python3

# initializing list
test_list = [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
 
# printing original list
print("The original list is : " + str(test_list))
 
# initializing custom list
cus_list = [4, 5, 7]
 
# performing sort using sorted()
res = sorted(test_list, key=lambda sub: len(
    [ele for ele in sub if ele in cus_list]))
 
# printing result
print("Sorted Matrix : " + str(res))

Output:

The original list is : [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
Sorted Matrix : [[9, 8, 2], [6, 5], [7, 1], [4, 5, 1, 7]]

Time Complexity: O(nlogn+mlogm) where n and m is the number of rows and columns in the list
Auxiliary Space: O(k) additional space of size k is created where n is the number of elements in the list

Method 3 : use a custom sorting algorithm.

steps for the approach:

Initialize an empty list to store the sorted sublists.
Loop through each sublist in the original list.
Count the number of elements in the sublist that are also in the custom list.
Create a tuple with the count and the sublist and append it to the empty list.
Sort the list of tuples by the count in ascending order.
Extract the sorted sublists from the sorted tuples and return the final result.

Python3

# initializing list
test_list = [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
# initializing custom list
cus_list = [4, 5, 7]
 
# custom sorting algorithm
def custom_sort(sublist):
    count = sum(1 for ele in sublist if ele in cus_list)
    return count
 
# creating a list of tuples with count and sublist
tuples_list = [(custom_sort(sublist), sublist) for sublist in test_list]
 
# sorting the list of tuples by count in ascending order
tuples_list.sort()
 
# extracting the sorted sublists from the tuples
sorted_list = [sublist for (count, sublist) in tuples_list]
 
# printing result
print("Sorted Matrix : " + str(sorted_list))

Output

Sorted Matrix : [[9, 8, 2], [6, 5], [7, 1], [4, 5, 1, 7]]

The time complexity of this approach is O(n * m * log(n)), where n is the number of sublists and m is the maximum length of a sublist.
The auxiliary space used by this approach is O(n * m), where n is the number of sublists and m is the maximum length of a sublist.

Method 4: Using list comprehension and key parameter

Initialize a list comprehension that iterates over each sublist in the test_list and filters out any elements that are not in the cus_list. Then, use len() to count the number of remaining elements in the sublist.
Use the sorted() function to sort the sublists based on the count of remaining elements, using the key parameter to pass in the list comprehension as the sorting criterion.
Assign the sorted sublists to the variable sorted_list.
Print the sorted sublists using the print() function.

Python3

test_list = [[4, 5, 1, 7], [6, 5], [9, 8, 2], [7, 1]]
cus_list = [4, 5, 7]
 
sorted_list = sorted(test_list, key=lambda x: len([i for i in x if i in cus_list]))
 
print("Sorted Matrix : " + str(sorted_list))

Output

Sorted Matrix : [[9, 8, 2], [6, 5], [7, 1], [4, 5, 1, 7]]

Time complexity: O(n^2), where n is the length of test_list since we are using list comprehension to iterate over each sublist and filter out elements.
Auxiliary space: O(n), where n is the length of test_list since we are storing the sorted sublists in a new list.