Given list of tuples, check if preceding element is smaller than the current element for each element in Tuple list.
Input : test_list = [(5, 1), (4, 9), (3, 5)]
Output : [[False, False], [False, True], [False, True]]
Explanation : First element always being False, Next element is checked for greater value.Input : test_list = [(1, 8), (2, 2), (3, 6), (4, 2)]
Output : [[False, True], [False, False], [False, True], [False, False]]
Explanation : 8 and 6 are greater cases in above cases, hence True.
Method #1 : Using list comprehension + enumerate() The combination of above functions can be used to solve this problem. In this, we perform the task of checking for greater value using one liner list comprehension and enumerate() is used to work with indices while nested iteration.
Python3
# Python3 code to demonstrate working of # Test if greater than preceding element in Tuple List# Using list comprehension + enumerate()# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original list print("The original list : " + str(test_list))# Test if greater than preceding element in Tuple List# Indices checked using enumerate() and True and false # values assigned in list comprehensionres = [[True if idx > 0 and j > i[idx - 1] else False for idx, j in enumerate(i)] for i in test_list]# printing result print("Filtered values : " + str(res)) |
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time complexity: O(n^2), where n is the length of the longest tuple in the list. This is because the program iterates through each element of each tuple in the list using nested loops, and the length of the inner loop depends on the length of the longest tuple.
Auxiliary space: O(n^2), as it creates a new 2-dimensional list of the same size as the input list to store the boolean values for each element in each tuple.
Method #2 : Using tee() + zip() + list comprehension This is one of the ways in which this task can be performed. In this, we extract elements and render them in tuple of size = 2, using tee(). List comprehension and zip() are used to construct the desired result.
Python3
# Python3 code to demonstrate working of # Test if greater than preceding element in Tuple List# Using tee() + zip() + list comprehensionfrom itertools import tee# helper functiondef pair(test_list): # pairing elements in 2 sized tuple x, y = tee(test_list) next(y, None) return zip(x, y)# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original list print("The original list : " + str(test_list))# Test if greater than preceding element in Tuple List# Using tee() + zip() + list comprehensionres = []for sub in test_list: # appending result by checking with Dual Pairs res.append(tuple((False, )) + tuple([x < y for x, y in pair(sub)])) # printing result print("Filtered values : " + str(res)) |
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time complexity: O(nm), where n is the length of the input list and m is the length of each tuple in the input list.
Auxiliary space: O(nm), where n is the length of the input list and m is the length of each tuple in the input list.
Method#3: Using a for loop and if-else statement
Python3
# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original listprint("The original list : " + str(test_list))# using for loop and if-else statementres = []for i in test_list: sub_list = [] for idx, j in enumerate(i): if idx > 0 and j > i[idx - 1]: sub_list.append(True) else: sub_list.append(False) res.append(sub_list)# printing resultprint("Filtered values : " + str(res))#This code is contributed by Vinay Pinjala. |
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time complexity: O(n)
Auxiliary Space : O(n)
Method #4: Using map() + lambda function
You can use the map() function along with a lambda function to apply the same logic used in the for loop and if-else statement in a more concise way:
Python3
# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original listprint("The original list : " + str(test_list))# using map() and lambda functionres = list(map(lambda x: [x[idx] > x[idx-1] if idx > 0 else False for idx in range(len(x))], test_list))# printing resultprint("Filtered values : " + str(res)) |
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time complexity: O(n*m), where n is the number of tuples in the test_list, and m is the maximum number of elements in a tuple.
Auxiliary space: O(nm), where n is the number of tuples in the test_list, and m is the maximum number of elements in a tuple.
Method #5: Using a generator expression
In this approach, the generator expression (j > i[idx – 1] for idx, j in enumerate(i) if idx > 0) generates a boolean value for each element in the tuple, indicating whether it is greater than the preceding element. The all() function is used to check if all these boolean values are true for a given tuple, and the result is stored in a list comprehension.
Python3
# Python3 code to demonstrate working of # Test if greater than preceding element in Tuple List# Using generator expression and all()# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original list print("The original list : " + str(test_list))# Test if greater than preceding element in Tuple List# Using generator expression and all()res = [all(j > i[idx - 1] for idx, j in enumerate(i) if idx > 0) for i in test_list]# printing result print("Filtered values : " + str(res)) |
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [False, False, True]
Time complexity: O(nm), where n is the length of the input list and m is the length of the tuples in the input list
Auxiliary space: O(n), as it creates a new list res with a length equal to the number of tuples in the input list.
Method #6: Using numpy:
Algorithm:
- Convert the given list of tuples to a NumPy array.
- Create a boolean NumPy array of the same shape as the input array, with all elements initialized to False.
- Compare each element in each row of the input array with its preceding element, using NumPy’s element-wise comparison.
- Replace the first element in each row of the resulting boolean array with False, since there is no preceding element for the first element in each row.
- Return the resulting boolean array as a list of lists.
Python3
import numpy as nptest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original listprint("The original list : " + str(test_list))arr = np.array(test_list)res = np.hstack((np.zeros((arr.shape[0], 1), dtype=bool), arr[:, 1:] > arr[:, :-1]))print("Filtered values : " + str(res.tolist()))#This code is contributed by Jyothi pinjala |
Output:
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time Complexity:
Creating a NumPy array from a list takes O(n) time where n is the number of elements in the list.
Comparing each element in each row of the input array with its preceding element using NumPy’s element-wise comparison takes O(m * n) time where m is the number of rows and n is the number of columns in the input array.
Replacing the first element in each row of the resulting boolean array with False takes O(m) time.
Converting the resulting boolean array to a list of lists takes O(m * n) time.
Therefore, the overall time complexity of the algorithm is O(m * n).
Auxiliary Space:
Creating a NumPy array from a list requires O(m * n) space, where m is the number of rows and n is the number of columns in the list of tuples.
Creating a boolean array of the same shape as the input array requires O(m * n) space.
Converting the boolean array to a list of lists requires O(m * n) space.
Therefore, the overall space complexity of the algorithm is O(m * n).
Method #7: Using pandas.DataFrame.diff()
- Convert the list of tuples to a pandas DataFrame using pd.DataFrame().
- Use the .diff() method with axis=1 to calculate the difference between each element in a row and the preceding element.
- Use the .gt() method to check which elements are greater than their preceding element.
- Convert the resulting DataFrame to a list of lists using .values.tolist().
Python3
import pandas as pd# initializing listtest_list = [(3, 5, 1), (7, 4, 9), (1, 3, 5)]# printing original list print("The original list : " + str(test_list))# convert list to DataFramedf = pd.DataFrame(test_list)# calculate difference between elements in each rowdiff = df.diff(axis=1)# check which elements are greater than their preceding elementres = diff.gt(0)# convert DataFrame to list of listsres = res.values.tolist()# printing result print("Filtered values : " + str(res)) |
Output-
The original list : [(3, 5, 1), (7, 4, 9), (1, 3, 5)] Filtered values : [[False, True, False], [False, False, True], [False, True, True]]
Time complexity: O(nm), where n is the number of rows and m is the number of elements in each row.
Space complexity: O(nm), for the pandas DataFrame and resulting list of lists.
