Open In App

Python | Check if a nested list is a subset of another nested list

Last Updated : 27 Apr, 2023
Improve
Improve
Like Article
Like
Save
Share
Report

Given two lists list1 and list2, check if list2 is a subset of list1 and return True or False accordingly. 

Examples:

Input : list1 = [[2, 3, 1], [4, 5], [6, 8]]
        list2 = [[4, 5], [6, 8]]
Output : True

Input : list1 = [['a', 'b'], ['e'], ['c', 'd']]
        list2 = [['g']]
Output : False

Let’s discuss few approaches to solve the problem. 

Approach #1 : Naive Approach Take a variable ‘exist’ which keeps track of each element, whether it is present in list1 or not. Start a loop and in each iteration ‘i’, check if ith element is present in list1. If present, set exist to True else false. 

Python3




# Python3 Program to Check is a nested
# list is a subset of another nested list
 
def checkSubset(list1, list2):
    l1, l2 = list1[0], list2[0]
    exist = True
    for i in list2:
        if i not in list1:
            exist = False
    return exist
     
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))


Output:

True

Time complexity: O(n), where n is length of list. 
Auxiliary space: O(1)

Approach #2 : Using Python set Convert each sublist of both the given nested lists to tuples, because sets can’t hold lists as they rely on their elements being immutable and lists are mutable. But converting them to tuple works well. After this, simply check if set of list2 is a subset of list1 or not. 

Python3




# Python3 Program to Check is a nested
# list is a subset of another nested list
 
def checkSubset(list1, list2):
    temp1 = []
    temp2 = []
    for i in list1:
        temp1.append(tuple(i))
    for i in list2:
        temp2.append(tuple(i))
     
    return set(temp2) < set(temp1)
     
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))


Output:

True

Time Complexity: O(n), where n is the length of the list test_dict
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the res list

Approach #3 : Using all and for loop This method uses a for loop to check if all elements(using all) belongs to list1 or not. 

Python3




# Python3 Program to Check is a nested
# list is a subset of another nested list
 
def checkSubset(list1, list2):
    return all(x in list1 for x in list2)
     
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))


Output:

True

Time complexity: O(mn), where m and n are the lengths of list1 and list2 respectively. 
Auxiliary space: O(1), because it only uses a few variables to store intermediate values and does not create any additional data structures.

Approach #4: Using map() and __contains__ In this approach we use Python map() using the “containment check” operator __contains__, checking whether list1 elements are contained withing list2 or not. 

Python3




# Python3 Program to Check is a nested
# list is a subset of another nested list
 
def checkSubset(list1, list2):
    return all(map(list1.__contains__, list2))
     
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))


Output:

True

Time complexity: O(N*M), where N is the number of sublists in list2 and M is the maximum number of elements in a sublist of list2. 
Auxiliary space: O(1), because it only uses a constant amount of extra memory to store the input lists and a few local variables.

Approach #5: Using issubset() method:

First converts the nested lists to sets of tuples, since sets cannot contain lists as elements. Then it uses the issubset method of sets to check if set2 is a subset of set1.

Python3




def is_subset(list1, list2):
    # convert both lists to sets of tuples
    set1 = set(tuple(x) for x in list1)
    set2 = set(tuple(x) for x in list2)
    # check if set2 is a subset of set1 using the intersection method
    return set2.issubset(set1)
 
# test the function
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(is_subset(list1, list2))  # should output True
 
list1 = [['a', 'b'], ['e'], ['c', 'd']]
list2 = [['g']]
print(is_subset(list1, list2))  # should output False
#This code is contributed by Edula Vinay Kumar Reddy


Output

True
False

Approach #6:  Using the ‘itertools.product’ function

Python3




import itertools
 
def checkSubset(list1, list2):
    # Convert the nested lists to sets so that they can be compared
    list1 = [set(i) for i in list1]
    list2 = [set(i) for i in list2]
 
    # Use the itertools.product method to get all possible combinations of elements in the two sets
    result = any(set1 == set2 for set1, set2 in itertools.product(list1, list2))
    return result
 
# Test the function with sample inputs
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))


Output

True

Time Complexity:  O(n^2) 
Auxiliary Space:  O(n^2) 

Approach #7:Using enumerate

The checkSubset function takes two lists, list1 and list2, as input and checks whether list2 is a subset of list1.

It does this by iterating through each row (row2) in list2 and checking if it is present in list1. It uses a nested loop to iterate through each row (row1) in list1 and compares it to row2. If a match is found, it sets the found variable to True and breaks out of the inner loop. If no match is found, it immediately returns False because list2 cannot be a subset of list1 if at least one row is not present in list1.

If all rows in list2 are present in list1, the function returns True.

In the driver code, list1 and list2 are defined and passed to the checkSubset function. The function is then called with these arguments, and the returned result is printed to the console.

Python3




def checkSubset(list1, list2):
    for row2 in list2:
        found = False
        for i, row1 in enumerate(list1):
            if row2 == row1:
                found = True
                break
        if not found:
            return False
    return True
 
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(checkSubset(list1, list2))
#This code is contributed by Vinay pinjala.


Output

True

Time Complexity:  O(n^2) 
Auxiliary Space:  O(n^2) 

Method#8: Using Recursive method.

Algorithm for the is_subset function:

  1. Check if list2 is empty. If it is, return True because an empty list is a subset of any other list.
  2. Check if list1 is empty. If it is, return False because it is not possible for list2 to be a subset of an empty list.
  3. Check if the first element of list2 is a subset of the first element of list1. Use the issubset method of the set class to perform this check.
  4. If the first element of list2 is a subset of the first element of list1, make a recursive call to is_subset with the rest of the elements of list1 and list2.
  5. If the first element of list2 is not a subset of the first element of list1, make a recursive call to is_subset with the rest of the elements of list1 and the entire list2.
  6. If no subset is found, return False.

Python3




def is_subset(list1, list2):
    if not list2:
        return True
    if not list1:
        return False
    if set(list2[0]).issubset(set(list1[0])):
        return is_subset(list1[1:], list2[1:])
    return is_subset(list1[1:], list2)
 
 
# Driver Code
list1 = [[2, 3, 1], [4, 5], [6, 8]]
list2 = [[4, 5], [6, 8]]
print(is_subset(list1, list2))
#This code is contributed by Tvsk.


Output

True

Time complexity:
The time complexity of this function is O(nm) where n is the length of list1 and m is the length of list2. This is because the function needs to check each element in list2 against each element in list1.

Auxiliary space complexity:
The auxiliary space complexity of this function is O(max(n, m)) because the function uses a set to check if one list is a subset of another. The size of the set depends on the size of the larger list, so the space complexity is proportional to the larger of the two lists. Additionally, the function makes recursive calls, so the space complexity is also proportional to the maximum depth of the recursion, which is at most min(n, m).



Previous Article
Next Article

Similar Reads

SymPy | Subset.subset() in Python
Subset.subset() : subset() is a sympy Python library function that returns the subset represented by the current instance. Syntax : sympy.combinatorics.subset.Subset.subset() Return : the subset represented by the current instance. Code #1 : subset() Example # Python code explaining # SymPy.Subset.subset() # importing SymPy libraries from sympy.com
1 min read
Python - Nested Dictionary Subset
Given a Nested Dictionary, test if another dictionary is a subset. Examples: Input : test_dict = {"gfg": 12, 'best' : {1 : 3, 4 : 3, 'geeks' : {8 : 7}}}, sub_dict = {8 : 7} Output : True Explanation : Required Nested dictionary present in Dictionary.Input : test_dict = {"gfg": 12, 'best' : {1 : 3, 4 : 3, 'geeks' : {8 : 7}}}, sub_dict = {9 : 7} Outp
7 min read
Python | Test if string is subset of another
Sometimes, while working with strings, we can have a problem in which we need to test if a string is a subsequence of another. This can have possible application in many domains including data science and day-day programming. Lets discuss certain ways in which this task can be performed. Method #1: Using all() This is one of the by which we can sol
7 min read
Python | Check if one list is subset of other
Sometimes we encounter the problem of checking if one list is just an extension of the list i.e just a superset of one list. These kinds of problems are quite popular in competitive programming. Having shorthands for it helps the cause. Let's discuss various ways to achieve this particular task. Method #1: Using all() function all() is used to chec
7 min read
Python | Check if a list is contained in another list
Given two lists A and B, write a Python program to Check if list A is contained in list B without breaking A's order. Examples: Input : A = [1, 2], B = [1, 2, 3, 1, 1, 2, 2] Output : TrueInput : A = ['x', 'y', 'z'], B = ['x', 'a', 'y', 'x', 'b', 'z'] Output : FalseApproach #1: Naive Approach A simple naive approach is to use two for loops and check
6 min read
Python Check if the List Contains Elements of another List
In Python programming, there can be a case where we have to check whether a list contains elements of Another List or not. In that case, we can follow several approaches for doing so. In this article, we will be discussing several approaches to check whether a list contains elements of another list or not. Python List Contains Elements of another L
2 min read
Python | Check if one dictionary is subset of other
Sometimes, while working with Python, we might have a problem in which we need to find, if a particular dictionary is part of another i.e it is a subset of another. A problem that has a huge potential in the web development domain, having knowledge of solving can be useful. Let's discuss certain ways in which this task can be performed. Method #1:
10 min read
Python | Check if one tuple is subset of other
Sometimes, while working with Python, we can work with different data and we might need to solve the problem of checking if one subset is part of another. Let's discuss certain ways in which this task can be performed. Method #1: Using issubset() We can solve this problem using type conversion of tuple into a set and then check if one tuple is subs
6 min read
PyQt5 - Check box checked state depending upon another check box
Sometimes while creating a GUI(Graphical User Interface) application there is a need to make lot of check boxes, and some check box depend upon the previous check box for example there are two following check box first check box is "Do you have Laptop ?" and second check box is "Your laptop has i7 Processor?" Here we can see that if first check box
3 min read
Python | Sectional subset sum in list
Some of the classical problems in the programming domain come from different categories and one among them is finding the sum of subsets. This particular problem is also common when we need to accumulate the sum and store consecutive group summations. Let's try different approaches to this problem in Python language. Method #1: Using list comprehen
7 min read
three90RightbarBannerImg