Sometimes, while working with Python Lists, we can have a problem in which we need to check if a particular sublist is contained in an exact sequence in a list. This task can have application in many domains such as school programming and web development. Let’s discuss certain ways in which this task can be performed.
Input : test_list = [5, 6, 3, 8, 2, 1, 7, 1], sublist = [8, 2, 3]
Output : FalseInput : test_list = [5, 6, 3, 8, 2, 3, 7, 1], sublist = [8, 2, 3]
Output : True
Method #1 : Using loop + list slicing
The combination of the above functions can be used to solve this problem. In this, we perform the task of checking for sublist by incremental slicing using the list slicing technique.
Python3
# Python3 code to demonstrate working of# Check for Sublist in List# Using loop + list slicing# initializing listtest_list = [5, 6, 3, 8, 2, 1, 7, 1]# printing original listprint("The original list : " + str(test_list))# initializing sublistsublist = [8, 2, 1]# Check for Sublist in List# Using loop + list slicingres = Falsefor idx in range(len(test_list) - len(sublist) + 1): if test_list[idx: idx + len(sublist)] == sublist: res = True break# printing resultprint("Is sublist present in list ? : " + str(res)) |
The original list : [5, 6, 3, 8, 2, 1, 7, 1] Is sublist present in list ? : True
Method #2 : Using any() + list slicing + generator expression
The combination of the above functions is used to solve this problem. In this, we perform the task of checking for any sublist equating to desired using any(), and list slicing is used to slice incremental list of the desired length.
Python3
# Python3 code to demonstrate working of# Check for Sublist in List# Using any() + list slicing + generator expression# initializing listtest_list = [5, 6, 3, 8, 2, 1, 7, 1]# printing original listprint("The original list : " + str(test_list))# initializing sublistsublist = [8, 2, 1]# Check for Sublist in List# Using any() + list slicing + generator expressionres = any(test_list[idx: idx + len(sublist)] == sublist for idx in range(len(test_list) - len(sublist) + 1))# printing resultprint("Is sublist present in list ? : " + str(res)) |
The original list : [5, 6, 3, 8, 2, 1, 7, 1] Is sublist present in list ? : True
Method #3 : Using for loop+in operator+len() method
Python3
# Python3 code to demonstrate working of# Check for Sublist in List# initializing listtest_list = [5, 6, 3, 8, 2, 1, 7, 1]# printing original listprint("The original list : " + str(test_list))# initializing sublistsublist = [8, 2, 7]# Check for Sublist in Listc=0res=Falsefor i in sublist: if i in test_list: c+=1if(c==len(sublist)): res=True# printing resultprint("Is sublist present in list ? : " + str(res)) |
The original list : [5, 6, 3, 8, 2, 1, 7, 1] Is sublist present in list ? : True
Method #4: Using the in operator with zip() and *
Step-by-step algorithm:
- Create the main list of integers to search for the sublist.
- Create the sublist to search for in the main list.
- Use a list comprehension to create a list of all possible sublists of the main list with the same length as the sublist.
- Use the zip function to group the elements of each sublist created in step 3.
- Compare each group of elements created in step 4 to the elements of the sublist.
- If a group of elements matches the elements of the sublist, return True. Otherwise, return False.
Python3
#This is a Python code file to check whether a sublist is present in a list#Initializing listtest_list = [5, 6, 3, 8, 2, 1, 7, 1]#Initializing sublist to be checkedsublist = [8, 2, 1]# printing original listprint("The original list : " + str(test_list))#Using list comprehension and zip function to check for sublistres = any(sublist == list(x) for x in zip(*[test_list[i:] for i in range(len(sublist))]))#Printing the resultprint("Is sublist present in list ? : " + str(res))#This code is contributed by Vinay Pinjala. |
The original list : [5, 6, 3, 8, 2, 1, 7, 1] Is sublist present in list ? : True
Time complexity: O(n*m), where n is the length of the main list and m is the length of the sublist.
Space complexity: O(n*m), where n is the length of the main list and m is the length of the sublist.
Method #5: Using set() Intersection
We can use the set intersection operation to check if all the elements of the sublist are present in the test_list. If the length of the intersection is equal to the length of the sublist, then we can conclude that the sublist is present in the test_list.
Python3
# Python3 code to demonstrate working of# Check for Sublist in List# initializing listtest_list = [5, 6, 3, 8, 2, 1, 7, 1]# printing original listprint("The original list : " + str(test_list))# initializing sublistsublist = [8, 2, 7]# Check for Sublist in Listif set(sublist).intersection(set(test_list)) == set(sublist): res = Trueelse: res = False# printing resultprint("Is sublist present in list ? : " + str(res)) |
The original list : [5, 6, 3, 8, 2, 1, 7, 1] Is sublist present in list ? : True
Time Complexity: O(n), where n is the length of the test_list, since we need to convert both the test_list and the sublist to sets and perform an intersection operation.
Auxiliary Space: O(k), where k is the length of the sublist, since we need to convert the sublist to a set.
Method#6: Recursive Method.
1. Define the recursive function `check_sublist_recursive` that takes in the original list (`test_list`) and the sublist (`sublist`) as arguments.
2. If the length of `sublist` is 0, return `True` since an empty list is a sublist of any list.
3. If the length of `test_list` is 0 and the length of `sublist` is not 0, return `False` since the `sublist` cannot be present in the `test_list`.
4. If the first element of `test_list` is equal to the first element of `sublist`, recursively call `check_sublist_recursive` with the first element of both lists removed.
5. If the first element of `test_list` is not equal to the first element of `sublist`, recursively call `check_sublist_recursive` with the first element of `test_list` removed.
6. Return the result of the recursive call.
Python3
def check_sublist_recursive(test_list, sublist): if len(sublist) == 0: return True if len(test_list) == 0: return False if test_list[0] == sublist[0]: return check_sublist_recursive(test_list[1:], sublist[1:]) else: return check_sublist_recursive(test_list[1:], sublist)test_list = [5, 6, 3, 8, 2, 1, 7, 1]sublist = [8, 2, 1]res = check_sublist_recursive(test_list, sublist)print("Is sublist present in list ? : " + str(res)) |
Is sublist present in list ? : True
