Python Program to find tuple indices from other tuple list

Given Tuples list and search list consisting of tuples to search, our task is to write a Python Program to extract indices of matching tuples.

Input : test_list = [(4, 5), (7, 6), (1, 0), (3, 4)], search_tup = [(3, 4), (8, 9), (7, 6), (1, 2)]
Output : [3, 1]
Explanation : (3, 4) from search list is found on 3rd index on test_list, hence included in result.

Input : test_list = [(4, 5), (7, 6), (1, 0), (3, 4)], search_tup = [(3, 4), (8, 9), (7, 6), (1, 0)]
Output : [3, 1, 2]
Explanation : (3, 4) from search list is found on 3rd index on test_list, hence included in result.

Method #1 : Using lookup dictionary + enumerate() + list comprehension

In this, a lookup dictionary is formed to map all the tuples with matching one’s indices. Then lookup dictionary is used to get indices of mapped tuples as result using list comprehension.

step by step approach:

1. Initialize a list of tuples named test_list containing some tuples.
2. Print the original list of tuples using the print() function and str() function to convert the list into a string.
3. Initialize another list of tuples named search_tup containing some tuples.
4. Create a lookup dictionary named lookup_dict using a dictionary comprehension where the keys are the tuples in test_list and the values are their indices.
5. Create a result list named res using a list comprehension that loops through each tuple idx in search_tup and checks if idx is present in the lookup_dict using the if idx in lookup_dict condition. If it is present, then the value of the corresponding key in the lookup_dict is appended to the res list.
6. Print the resulting list of tuple indices using the print() function and str() function to convert the list into a string.

Output:

The original list is : [(4, 5), (7, 6), (1, 0), (3, 4)]
The match tuple indices : [3, 1]

Time complexity: O(n) – where n is the length of the test_list or search_tup, whichever is larger. The creation of the lookup_dict has a time complexity of O(n), and the list comprehension has a time complexity of O(k) where k is the number of matches found in search_tup.
Auxiliary space: O(n) – where n is the length of the test_list. The lookup_dict takes up O(n) space.

Method #2 : Using list comprehension + enumerate()

In this, we perform the task of getting indices using enumerate(), and list comprehension is used for the task of iteration of all the elements of tuple and matching for equality.

Output:

The original list is : [(4, 5), (7, 6), (1, 0), (3, 4)]
The match tuple indices : [1, 3]

Time Complexity: O(N)
Auxiliary Space: O(N)

Method #3 : Using index() method

The original list is : [(4, 5), (7, 6), (1, 0), (3, 4)]
The match tuple indices : [3, 1]

Time Complexity: O(N)
Auxiliary Space: O(N)

Method #4: Using operator.countOf() method

The original list is : [(4, 5), (7, 6), (1, 0), (3, 4)]
The match tuple indices : [3, 1]

Time Complexity: O(N)
Auxiliary Space: O(N)

Method 5:  using the filter() function

The original list is : [(4, 5), (7, 6), (1, 0), (3, 4)]
The match tuple indices : [1, 3]

Time complexity: O(n), where n is the length of the list test_list.
Auxiliary space: O(n) as well, since we are storing the indices of the matching tuples in the res list. 

Method 6: Using the map function and a lambda function:

We can use the map function to apply a lambda function to each tuple in search_tup. The lambda function checks if the tuple exists in test_list using the in operator and returns the index using the index method if it does, and None otherwise. We then convert the map object to a list and filter out the None values using a list comprehension.

The match tuple indices : [3, 1]

Time complexity: O(mn), where m is the length of search_tup and n is the length of test_list. .
Auxiliary space: O(m), where m is the length of search_tup.

Method 7: Using nested loops and tuple comparison.

Algorithm:

1. Initialize an empty list res to store the indices of matching tuples.
2. Iterate over each tuple tup in the search_tup list.
3. Iterate over each tuple lst_tup in the test_list list.
4. Check if tup is equal to lst_tup. If they are equal, append the index of lst_tup to res and break the inner loop.
5. After both loops have completed, print the list of indices res.

The match tuple indices : [3, 1]

Time Complexity:

The time complexity of this algorithm is O(N*M), where N is the length of the search_tup list and M is the length of the test_list list.
This is because we are iterating over each tuple in search_tup and checking it against each tuple in test_list.
In the worst-case scenario, where no tuples match, we will iterate over all N*M possible combinations of tuples.
However, in the best-case scenario, where the first tuple in search_tup matches the first tuple in test_list, we only need to iterate over one combination of tuples.
In general, the time complexity of this algorithm depends on the specific input data and the distribution of matching tuples between the two lists.
Space Complexity:

The space complexity of this algorithm is O(1), as we are only using a fixed amount of memory to store the variables res, i, j, tup, and lst_tup.
We do not create any new lists or dictionaries, so the space required by the algorithm does not depend on the size of the input data.

manjeet_04

Follow

Improve