Sometimes, while working with Python records, we can have a problem in which we need to find the tuple nearest to certain tuple, query on a particular index. This kind of problem can have applications in data domains such as web development. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)] tup = (17, 23) K = 2
Output : (19, 23)Input : test_list = [(3, 4, 9), (5, 6, 7)] tup = (1, 2, 5) K = 3
Output : (5, 6, 7)
Method #1: Using enumerate() + loop The combination of above functions offer brute force way to solve this problem. In this, we use enumerate() to monitor index and abs() to keep the minimum difference updated checked for each element over a loop.
Python3
# Python3 code to demonstrate working of # Closest Pair to Kth index element in Tuple# Using enumerate() + loop# initializing listtest_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]# printing original listprint("The original list is : " + str(test_list))# initializing tupletup = (17, 23)# initializing K K = 1# Closest Pair to Kth index element in Tuple# Using enumerate() + loopmin_dif, res = 999999999, Nonefor idx, val in enumerate(test_list): dif = abs(tup[K - 1] - val[K - 1]) if dif < min_dif: min_dif, res = dif, idx# printing result print("The nearest tuple to Kth index element is : " + str(test_list[res])) |
The original list is : [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)] The nearest tuple to Kth index element is : (19, 23)
Time complexity: O(n), where n is the length of the test_list.
Auxiliary space: O(1), as we only use a constant number of variables regardless of the input size.
Method #2: Using min() + lambda The combination of above functions offer shorthand to solve this problem. In this, we use min() to find minimum element difference and lambda function is used to perform iterations and computations.
Python3
# Python3 code to demonstrate working of # Closest Pair to Kth index element in Tuple# Using min() + lambda# initializing listtest_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]# printing original listprint("The original list is : " + str(test_list))# initializing tupletup = (17, 23)# initializing K K = 1# Closest Pair to Kth index element in Tuple# Using min() + lambdares = min(range(len(test_list)), key = lambda sub: abs(test_list[sub][K - 1] - tup[K - 1]))# printing result print("The nearest tuple to Kth index element is : " + str(test_list[res])) |
The original list is : [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)] The nearest tuple to Kth index element is : (19, 23)
Time complexity: O(n), where n is the length of the input list
Auxiliary space: O(1), since we are not using any additional data structures or variables proportional to the size of the input list.
Method#3:Using a lambda function and the min() function
Step-by-step algorithm:
- Initialize the list of tuples, the target tuple and the index K.
- Use the min() function and a lambda function to find the tuple in the list with the smallest absolute difference between its Kth element and the Kth element of the target tuple.
- Assign the result of the min() function to a variable named “res”.
- Print the value of “res” as the nearest tuple to the Kth index element of the target tuple.
Python3
# initializing listtest_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]# initializing tupletup = (17, 23)# initializing KK = 1# Using a lambda function and the min() functionres = min(test_list, key=lambda x: abs(x[K-1] - tup[K-1]))# printing resultprint("The nearest tuple to Kth index element is : " + str(res)) |
The nearest tuple to Kth index element is : (19, 23)
Time complexity: O(n), where n is the length of the list of tuples. This is because the min() function iterates over the list once to find the tuple with the smallest absolute difference between its Kth element and the Kth element of the target tuple.
Auxiliary space: O(1), since we only store a constant amount of data, such as the list of tuples, the target tuple, the index K, and the result tuple.
Method#4:Using the heapq.nsmallest() function:
Algorithm:
1.Initialize a list of tuples.
2.Initialize the tuple we want to find the closest match for.
3.Initialize the index of the tuple we want to compare.
4.Use the heapq.nsmallest() function to find the smallest element in the list based on the difference between the tuple elements at the specified index.
5.Return the closest tuple.
Python3
import heapq# initializing the list of tuplestest_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]# initializing the target tupletup = (17, 23)# initializing the index of the element to compare in each tupleK = 1# using the heapq.nsmallest() function to get the tuple with the smallest difference between the Kth element and the corresponding element in the target tupleres = heapq.nsmallest(1, test_list, key=lambda x: abs(x[K-1] - tup[K-1]))[0]# printing the resultprint("The nearest tuple to Kth index element is : " + str(res))#This code is contributed by Jyothi pinjala. |
The nearest tuple to Kth index element is : (19, 23)
Time complexity:
The time complexity of this code is O(nlogk), where n is the number of elements in the list and k is the value passed as the first argument to heapq.nsmallest(). In this case, k is 1, so the time complexity is effectively O(log n).
Space complexity:
The space complexity of this code is O(k), where k is the value passed as the first argument to heapq.nsmallest(). In this case, k is 1, so the space complexity is effectively constant.
Method 5 : using the sorted() function with a custom key.
step-by-step approach :
Step 1: Initialize the list of tuples, the target tuple, and the index of the element to compare in each tuple.
Step 2: Define a custom key function that takes a tuple as input and returns the absolute difference between the Kth element of the tuple and the corresponding element in the target tuple.
Step 3: Use the sorted() function to sort the list of tuples based on the custom key function.
Step 4: Retrieve the first tuple from the sorted list.
Step 5: Print the result.
Python3
# initializing the list of tuplestest_list = [(3, 4), (78, 76), (2, 3), (9, 8), (19, 23)]# initializing the target tupletup = (17, 23)# initializing the index of the element to compare in each tupleK = 1# define a custom key functiondef key_func(t): return abs(t[K-1] - tup[K-1])# use the sorted() function to sort the list of tuples based on the custom key functionsorted_list = sorted(test_list, key=key_func)# retrieve the first tuple from the sorted listres = sorted_list[0]# print the resultprint("The nearest tuple to Kth index element is : " + str(res)) |
The nearest tuple to Kth index element is : (19, 23)
Time complexity: O(n log n), where n is the length of the list of tuples. The sorted() function uses the Timsort algorithm, which has a time complexity of O(n log n).
Auxiliary space: O(n), where n is the length of the list of tuples. The sorted() function creates a new sorted list, which has the same length as the original list.
