Python – Matrix Row subset

Sometimes, while working with Python Matrix, one can have a problem in which, one needs to extract all the rows that are a possible subset of any row of other Matrix. This kind of problem can have applications in data domains as a matrix is a key data type in those domains. Let’s discuss certain ways in which this problem can be solved.

Input : test_list = [[4, 5, 7], [2, 3, 4], [9, 8, 6]], check_matr = [[2, 3], [1, 2], [9, 0]] 
Output : [[2, 3]] 

Input : test_list = [[4, 1, 2], [2, 3, 4], [9, 8, 0]], check_matr = [[2, 3], [1, 2], [9, 0]] 
Output : [[2, 3], [1, 2], [9, 0]]

Method #1: Using any() + all() + list comprehension

The combination of the above functions offers a way in which this problem can be solved. In this, we check for the occurrence of all elements of row using all(), and any() is used to match any row of the Matrix. List comprehension is used to bind the logic together. 

The original list is : [[4, 5, 7], [2, 3, 4], [9, 8, 0]]
Matrix row subsets : [[2, 3], [9, 0]]

Time complexity: O(n^3) where n is the size of the input matrix. This is because the program uses nested loops to iterate over the elements of the input matrix and the check matrix, and the all() and any() functions also iterate over the lists. Therefore, the time complexity of the program can be expressed as O(n * m * k), where n is the number of rows in the check matrix, m is the number of rows in the input matrix, and k is the number of elements in each row.

Auxiliary space: O(n), where n is the size of the input matrix. This is because the program creates a new list res to store the matrix row subsets. The size of this list is at most equal to the number of rows in the input matrix. Therefore, the space complexity of the program can be expressed as O(m), where m is the number of rows in the input matrix.

Method #2: Using product() + set() + list comprehension

The combination of the above functions can be used for this task. In this, we perform the task of nested loop using product() and set() conversion to check for subset of one container over another. List comprehension is used to bind all together. 

The original list is : [[4, 5, 7], [2, 3, 4], [9, 8, 0]]
Matrix row subsets : [[2, 3], [9, 0]]

Time complexity: O(n^2 * m^2), where n is the number of rows in check_matr and m is the number of rows in test_list.
Auxiliary space: O(m), where m is the number of elements in the longest row of test_list. 

Method 3: Using nested loops and set intersection to find the row subsets

In this code loops over each row in check_matr and each list in test_list, then checks if the set of the current row is a subset of the set of the current list using set.issubset(). If it is, the row is added to the result list.

Matrix row subsets:  [[2, 3], [9, 0]]

Time Complexity: O(n * m * k) where n, m, and k are the lengths of check_matr, test_list.
Auxiliary Space: O(1) since it uses a constant amount of extra space to store variables like res, row, and lst.

Method #4: Using map() and set operations

1. Initialize the lists:
2. Define a function is_subset(a, b) that takes two lists as arguments and returns True if a is a subset of b, False otherwise:
3. Use map() to apply the function to each pair of sublists from check_matr and test_list:
4. Print the result:

Matrix row subsets : [[2, 3], [9, 0]]

Time complexity: O(nmk) where n is the length of test_list, m is the length of check_matr, and k is the length of the sublists.
Auxiliary space: O(1) since we are not storing any additional data structures.

Method #5: Using set comprehension and issubset() method

1. Initialize an empty list res to store the row subsets.
2. Iterate through each row a in check_matr.
3. Using set comprehension, create a set set_a from the elements of a.
4. Iterate through each row b in test_list.
5. Using set comprehension, create a set set_b from the elements of b.
6. Check if set_a is a subset of set_b using the issubset() method.
7. If set_a is a subset of set_b, append a to the res list.
8. Print the res list.

The original list is : [[4, 5, 7], [2, 3, 4], [9, 8, 0]]
Matrix row subsets : [[2, 3], [9, 0]]

Time complexity: O(nmk) where n is the number of rows in check_matr, m is the number of rows in test_list, and k is the length of each row.
Auxiliary space: O(k) where k is the length of each row.

Method 6: Use the built-in function filter() along with a lambda function 

1. Create two matrices test_list and check_matr containing integer values.
2. Define a lambda function is_subset that takes a row from check_matr and returns True if it is a subset of any row in test_list.
3. Create a list res to store the rows of check_matr that are subsets of test_list.
4. Use the filter() function to apply the is_subset function to each row in check_matr.
5. Convert the filtered result into a list and store it in res.
6. Print the resulting list res to show the rows of check_matr that are subsets of test_list.

Matrix row subsets:  [[2, 3], [9, 0]]

Time complexity: O(n^2), where n is the number of elements in the input matrices
Auxiliary space: O(1), because it does not use any additional data structures besides the input matrices and the output list.