Python – Tuple List intersection (Order irrespective)

Given list of tuples, perform tuple intersection of elements irrespective of their order.

Input : test_list1 = [(3, 4), (5, 6)], test_list2 = [(5, 4), (4, 3)] 
Output : {(3, 4)} 
Explanation : (3, 4) and (4, 3) are common, hence intersection ( order irrespective).

Input : test_list1 = [(3, 4), (5, 6)], test_list2 = [(5, 4), (4, 5)] 
Output : set() 
Explanation : No intersecting element present. 

Method #1 : Using sorted() + set() + & operator + list comprehension 
The combination of above functions can be used to solve this problem. In this, we sort the tuples, and perform intersection using & operator. 

The original list 1 is : [(3, 4), (5, 6), (9, 10), (4, 5)]
The original list 2 is : [(5, 4), (3, 4), (6, 5), (9, 11)]
List after intersection : {(4, 5), (3, 4), (5, 6)}

Time complexity: O(n*nlogn), where n is the length of the test_list. The sorted() + set() + & operator + list comprehension takes O(n*nlogn) time
Auxiliary Space: O(n), extra space of size n is required

Method #2 : Using list comprehension + map() + frozenset() + & operator 
The combination of above functions can be used to perform this task. In this, we perform the task of conversion of innercontainers to sets, which orders it, and performs the intersection. Frozenset is used as its hashable, and map() requires hashable data type as argument.

The original list 1 is : [(3, 4), (5, 6), (9, 10), (4, 5)]
The original list 2 is : [(5, 4), (3, 4), (6, 5), (9, 11)]
List after intersection : {frozenset({4, 5}), frozenset({5, 6}), frozenset({3, 4})}

Method 3: Using the built-in intersection() method of sets.

Step-by-step approach:

• Convert test_list1 and test_list2 into sets of frozensets. A frozenset is used because it is immutable and can be added to a set.
• Use the intersection() method to find the intersection of the two sets.
• Loop through the resulting set and convert each frozenset back into a tuple.
• Append each tuple to a new list result.
• Print the result.

Below is the implementation of the above approach:

The original list 1 is : [(3, 4), (5, 6), (9, 10), (4, 5)]
The original list 2 is : [(5, 4), (3, 4), (6, 5), (9, 11)]
List after intersection : [(4, 5), (5, 6), (3, 4)]

Time complexity: O(n), where n is the length of the longer of the two input lists. 
Auxiliary space: O(n), where n is the length of the intersection of the two sets.

Method #4: Using a dictionary and list comprehension

Step-by-step approach:

• Create an empty dictionary called freq_dict
• Loop through test_list1 and test_list2
  • For each tuple, sort it and convert it to a string
  • Check if the string is in freq_dict
  • If it is, increment the count of the string
  • If it isn’t, add the string as a key with a count of 1
• Create a list comprehension using the tuples from test_list1 that appear in test_list2 by checking the count of the sorted string in freq_dict
• Print the resulting list

Below is the implementation of the above approach:

List after intersection: [(3, 4), (5, 6), (4, 5)]

Time complexity: O(n log n) due to sorting the tuples
Auxiliary space: O(n) to store the dictionary

Method #5: Using nested loops

Step-by-step approach:

• Initialize an empty list called res.
• Loop through each tuple in test_list1.
• For each tuple in test_list1, loop through each tuple in test_list2.
• If the tuples have the same elements (in any order), append the tuple to res.
• Return res.

Below is the implementation of the above approach:

List after intersection : [(3, 4), (5, 6), (4, 5)]

Time complexity: O(n^2), where n is the length of the lists.
Auxiliary space: O(k), where k is the number of tuples that are common to both lists.

manjeet_04

Follow

Improve