Sometimes, while working with Python records, we can have a problem in which we need to remove records on the basis of presence of consecutive K elements in tuple. This kind of problem is peculiar but can have applications in data domains. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [(4, 5), (5, 6), (1, 3), (0, 0)] K = 0
Output : [(4, 5), (5, 6), (1, 3)]
Input : test_list = [(4, 5), (5, 6), (1, 3), (5, 4)] K = 5
Output : [(4, 5), (5, 6), (1, 3), (5, 4)]
Method #1 : Using zip() + list comprehension The combination of above functions can be used to solve this problem. In this, we need to combine two consecutive segments using zip() and perform the comparison in list comprehension.
Python3
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
print("The original list is : " + str(test_list))
K = 6
res = [idx for idx in test_list if (K, K) not in zip(idx, idx[1:])]
print("The records after removal : " + str(res))
|
Output :
The original list is : [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
The records after removal : [(4, 5, 6, 3), (1, 3, 5, 6)]
Time complexity: O(n*m), where n is the number of tuples in the list and m is the number of elements in each tuple.
Auxiliary space: O(n), where n is the number of tuples in the list. This is because the program creates a new list to store the filtered tuples.
Method #2 : Using any() + list comprehension The combination of above functions can be used to solve this problem. In this, we check for consecutive elements using any() and list comprehension is used to remake the list.
Python3
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
print("The original list is : " + str(test_list))
K = 6
res = [idx for idx in test_list if not any(idx[j] == K and idx[j + 1] == K for j in range(len(idx) - 1))]
print("The records after removal : " + str(res))
|
Output :
The original list is : [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
The records after removal : [(4, 5, 6, 3), (1, 3, 5, 6)]
The time complexity of the given code is O(nm), where n is the number of tuples in the list and m is the maximum length of a tuple.
The auxiliary space used by the code is O(n), which is the space required to store the new list of tuples after the removal of consecutive K element records.
Method #3: Using a for loop and a temporary list
This approach uses a nested for loop to iterate through each tuple in the list and each element within the tuple to check if there are any consecutive K elements. If there are, the tuple is skipped and not added to a temporary list. After iterating through all the tuples, the resulting temporary list is assigned to res.
Python3
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
K = 6
temp_list = []
for item in test_list:
skip = False
for i in range(len(item)-1):
if item[i] == K and item[i+1] == K:
skip = True
break
if not skip:
temp_list.append(item)
res = temp_list
print("The records after removal : ", res)
|
Output
The records after removal : [(4, 5, 6, 3), (1, 3, 5, 6)]
Time complexity: O(N*M), where N is the number of tuples in the list and M is the maximum length of a tuple..
Auxiliary space: O(N*M), where N is the number of tuples in the list and M is the maximum length of a tuple.
Method #4: Using filter() function
In this method, we use the filter() function along with a lambda function. The lambda function checks if any consecutive elements in a tuple are equal to K using zip() and any() functions. If they are, then the filter() function removes that tuple from the list. The resulting list contains all tuples that do not have consecutive elements equal to K.
Python3
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
K = 6
res = list(filter(lambda x: not any(i == j == K for i, j in zip(x, x[1:])), test_list))
print("The records after removal : ", res)
|
Output
The records after removal : [(4, 5, 6, 3), (1, 3, 5, 6)]
Time complexity: O(n*m), where n is the number of tuples in the list and m is the length of each tuple.
Auxiliary space: O(n), where n is the number of tuples in the list.
Method 5: Using the itertools module
- Import the itertools module.
- Initialize an empty list called res.
- Use the itertools.filterfalse() function to remove items that contain consecutive occurrences of K.
- Convert the result to a list and assign it to res.
- Return res.
Python3
import itertools
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
K = 6
res = list(itertools.filterfalse(lambda item: any(item[i] == K and item[i+1] == K for i in range(len(item)-1)), test_list))
print("The records after removal : ", res)
|
Output
The records after removal : [(4, 5, 6, 3), (1, 3, 5, 6)]
Time complexity: O(n^2), where n is the length of the longest item in test_list.
Auxiliary space: O(n), where n is the number of items in test_list.
Method 6: Using numpy:
Algorithm:
- Convert the list of tuples to a 2D NumPy array using np.array().
- Check if consecutive elements in each row are equal to K using the element-wise == operator and logical & operator to get a boolean array.
- Use np.any() with axis=1 to check if there is any True value in each row of the boolean array. This gives us a 1D boolean mask.
- Use np.logical_not() to negate the mask so that True values become False and vice versa.
- Filter the rows based on the mask using NumPy boolean indexing.
- Return the filtered rows as a NumPy array.
Python3
import numpy as np
test_list = [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
K = 6
print("The original list is : " + str(test_list))
arr = np.array(test_list)
mask = np.logical_not(np.any((arr[:,:-1] == K) & (arr[:,1:] == K), axis=1))
res = arr[mask]
print("The records after removal : ", res)
|
Output:
The original list is : [(4, 5, 6, 3), (5, 6, 6, 9), (1, 3, 5, 6), (6, 6, 7, 8)]
The records after removal : [[4 5 6 3]
[1 3 5 6]]
Time complexity: O(nm), where n is the number of tuples and m is the number of elements in each tuple. Converting the list to a NumPy array takes O(nm) time. Checking for consecutive elements and applying the mask takes O(nm) time. Filtering the rows takes O(nm) time in the worst case if all rows pass the filter.
Space complexity: O(nm), where n is the number of tuples and m is the number of elements in each tuple. This is the space required to store the NumPy array.
Please Login to comment...