Given a range, sort tuple Matrix by total range covered in a given range. [Considering tuples which completely lie within range].
Input : test_list = [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]], i, j = 2, 15
Output : [[(3, 16)], [(1, 5), (6, 10), (10, 15)], [(1, 3), (9, 13)], [(2, 4), (6, 8), (9, 14)]]
Explanation : 0 < 4 < 4 < 9, is the magnitude of range covered in tuples lists.Input : test_list = [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)]], i, j = 2, 15
Output : [[(3, 16)], [(1, 5), (6, 10), (10, 15)], [(2, 4), (6, 8), (9, 14)]]
Explanation : 0 < 4 < 9, is the magnitude of range covered in tuples lists.
Method #1 : Using sort() + sum()
In this, inplace sorting is performed using sort(), and summation of ranges in the given range is performed using sum() and list comprehension with conditions.
Python3
# Python3 code to demonstrate working of# Sort by range inclusion# Using sort() + sum()def range_sum(row): # summing in range element return sum([abs(sub[1] - sub[0]) for sub in row if sub[0] > i and sub[0] < j and sub[1] > i and sub[1] < j])# initializing listtest_list = [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [ (2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]]# printing original listprint("The original list is : " + str(test_list))# initializing rangei, j = 2, 15# inplace sorting using sort()test_list.sort(key=range_sum)# printing resultprint("Sorted List : " + str(test_list)) |
Output:
The original list is : [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]] Sorted List : [[(3, 16)], [(1, 5), (6, 10), (10, 15)], [(1, 3), (9, 13)], [(2, 4), (6, 8), (9, 14)]]
Time Complexity: O(nlogn)
Auxiliary Space: O(1)
Method #2 : Using sorted() + lambda + sum()
In this, we perform task of sorting using sorted() and utility injection using lambda function, the summation is performed using sum().
Python3
# Python3 code to demonstrate working of# Sort by range inclusion# Using sorted() + lambda + sum()# initializing listtest_list = [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [ (2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]]# printing original listprint("The original list is : " + str(test_list))# initializing rangei, j = 2, 15# sorting using sorted() + lambdares = sorted(test_list, key=lambda row: sum( [abs(sub[1] - sub[0]) for sub in row if sub[0] > i and sub[0] < j and sub[1] > i and sub[1] < j]))# printing resultprint("Sorted List : " + str(res)) |
Output:
The original list is : [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]] Sorted List : [[(3, 16)], [(1, 5), (6, 10), (10, 15)], [(1, 3), (9, 13)], [(2, 4), (6, 8), (9, 14)]]
Time Complexity: O(n*logn), where n is the length of the input list. This is because we’re using the built-in sorted() function which has a time complexity of O(nlogn) in the worst case.
Auxiliary Space: O(1), as we’re not using any additional space other than the input list itself.
METHOD 3:Using filter() function and Sorting
APPROACH:
we use the filter() function to create a new list based on the range inclusion of each sublist. Then we sort the sublists based on their range inclusion.
ALGORITHM:
1.Start by defining the input variables test_list, i, and j.
2.Use the filter() function to iterate through each tuple in the test_list and check if any of the values in the tuple fall within the range [i,j].
3.Use the sorted() function to sort the filtered list by whether each tuple contains a value within the range [i,j]. Sort the list in reverse order so that tuples that contain values within the range [i,j] are first.
4.Print the sorted list.
Python3
test_list = [[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]]i, j = 2, 15filtered_list = list(filter(lambda x: any(i <= a <= j or i <= b <= j for a, b in x), test_list))sorted_list = sorted(filtered_list, key=lambda x: any(i <= a <= j or i <= b <= j for a, b in x), reverse=True)print(sorted_list) |
[[(1, 5), (6, 10), (10, 15)], [(3, 16)], [(2, 4), (6, 8), (9, 14)], [(1, 3), (9, 13)]]
Time Complexity: O(N*log(N)), where N is the number of sublists.
Space Complexity: O(N), where N is the number of sublists.
