Sometimes, while working with Python tuples, we can have a problem in which we need to extract all the tuples, which have all the elements in target tuple. This problem can have application in domains such as web development. Let’s discuss certain way in which this problem can be solved.
Input : test_list = [(5, 6, 6), (4, 2, 7), (9, 6, 5, 6)] test_tuple = (6, 6) Output : [(5, 6, 6), (9, 6, 5, 6)] Input : test_list = [(5, 6, 6), (4, 2, 6), (9, 6, 5, 6)] test_tuple = (6, ) Output : [(5, 6, 6), (4, 2, 6), (9, 6, 5, 6)]
Method : Using Counter() + list comprehension + all() The combination of above functions can be used to solve this problem. In this, we perform the task of counting using Counter(). The all(), is used to check if all elements form the subset and list comprehension is used to bind all the logic in one block.
Python3
# Python3 code to demonstrate working of # Extract tuple supersets from List # Using all() + list comprehension + Counter from collections import Counter # initializing list test_list = [( 5 , 6 , 8 ), ( 4 , 2 , 7 ), ( 9 , 6 , 5 , 6 )] # printing original list print ("The original list is : " + str (test_list)) # initializing tuple test_tup = ( 6 , 6 , 5 ) # Extract tuple supersets from List # Using all() + list comprehension + Counter res = [sub for sub in test_list if all (Counter(sub)[x] > = Counter(test_tup)[x] for x in Counter(test_tup))] # printing result print ("The superset tuples : " + str (res)) |
The original list is : [(5, 6, 8), (4, 2, 7), (9, 6, 5, 6)] The superset tuples : [(9, 6, 5, 6)]
Time Complexity: O(n*n) where n is the number of elements in the in the list “test_list”. The Counter() + list comprehension + all() is used to perform the task and it takes O(n*n) time.
Auxiliary Space: O(n), the algorithm uses an additional list to store the result, thus consuming linear space which is O(n).
Method#2 : Using filter() Function
Approach
Iterate through each tuple in the list.Check if the test tuple is a subset of the current tuple using the set() method.
If it is a subset, add the current tuple to a new list, which will contain all the supersets of the test tuple. Return the new list of supersets
Algorithm
1. Initialize a new empty list called result.
2. Loop through each tuple in the given list.
3. If the test tuple is a subset of the current tuple, append the current tuple to the result list.
4. Return the result list.
Python3
def extract_supersets(test_list, test_tuple): #define inputs return list ( filter ( lambda t: set (t).issuperset( set (test_tuple)), test_list)) #using filter find tuples test_list = [( 5 , 6 , 6 ), ( 4 , 2 , 7 ), ( 9 , 6 , 5 , 6 )] #inputs# test_tuple = ( 6 , 6 ) print (extract_supersets(test_list, test_tuple)) #print result |
[(5, 6, 6), (9, 6, 5, 6)]
Time complexity: O(n*m) where n is the length of the list and m is the length of the longest tuple in the list. This is because we need to loop through each tuple in the list, and also need to check if the test tuple is a subset of each tuple, which takes O(m) time.
Space complexity: O(k) where k is the number of supersets found. This is because we need to create a new list to store the supersets.
Method #3:Using for loop
Algorithm
- Define a function called extract_supersets which takes two arguments: test_list and test_tuple.
- Inside the function, initialize an empty list called supersets.
- Loop through each tuple in test_list.
- Check if the set of the tuple is a superset of the set of test_tuple using the issuperset() method.
- If it is a superset, append the tuple to the supersets list.
- Return the supersets list.
- Call the extract_supersets() function with the given test_list and test_tuple as arguments.
- Print the result of the function call.
Python3
def extract_supersets(test_list, test_tuple): result = [] for t in test_list: if set (test_tuple).issubset( set (t)): result.append(t) return result test_list = [( 5 , 6 , 6 ), ( 4 , 2 , 7 ), ( 9 , 6 , 5 , 6 )] test_tuple = ( 6 , 6 ) print (extract_supersets(test_list, test_tuple)) #This code is contributed by Vinay Pinjala. |
[(5, 6, 6), (9, 6, 5, 6)]
The time complexity of this code is O(n*k), where n is the length of test_list and k is the length of the largest tuple in test_list. This is because we are iterating over each tuple in test_list and performing a set operation that takes O(k) time.
The space complexity of this code is O(1) since we are not using any additional space beyond the input and output lists.
Approach#4: using subset + len
We use filter function with a lambda function to filter out the tuples in the list which are the supersets of the given tuple.
Algorithm
1. Define the input list and tuple.
2. Use filter function with lambda to filter out the tuples which are supersets of the given tuple.
3. Convert the filtered tuples to list.
4. Return the list.
Python3
import itertools test_list = [( 5 , 6 , 6 ), ( 4 , 2 , 7 ), ( 9 , 6 , 5 , 6 )] test_tuple = ( 6 , 6 ) result_list = list ( filter ( lambda x: set (test_tuple).issubset(x) and len (x) > len (test_tuple), test_list)) print (result_list) |
[(5, 6, 6), (9, 6, 5, 6)]
Time complexity: O(n*m), where n is the length of the input list and m is the length of the longest tuple in the list.
Auxiliary Space: O(1) (excluding the space required to store the result list).