Given a List of sets, the task is to write a Python program tocompare elements with argument set, and return one with maximum matching elements.
Examples:
Input : test_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}], arg_set = {9, 6, 5, 3}
Output : {9, 3, 5, 7}
Explanation : Resultant set has maximum matching elements.Input : test_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}], arg_set = {4, 6, 5, 3}
Output : {2, 3, 4, 5}
Explanation : Resultant set has maximum matching elements.
Method 1: Using loop + set.intersection()
In this, we perform task of getting all the common elements with argument set using intersection(), and get its length using len(), and maximum length and set is compared and updated during iteration.
Python3
# Python3 code to demonstrate working of# Most common elements set# Using loop + intersection()# initializing listtest_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}]# printing original listprint("The original list is : " + str(test_list))# initializing arg_setarg_set = {9, 6, 5, 3}res = set()max_len = 0for sub in test_list: # updating max value on occurrence if len(sub.intersection(arg_set)) > max_len: max_len = len(sub.intersection(arg_set)) res = sub# printing resultprint("Max Set intersection : " + str(res)) |
Output:
The original list is : [{2, 3, 4, 5}, {8, 2, 4, 7}, {1, 2, 3, 4}, {9, 3, 5, 7}]
Max Set intersection : {9, 3, 5, 7}
Method 2 : Using max() + list comprehension + intersection()
In this, initial step is to check for the lengths of all intersected set results and get maximum using max(). Next, task of getting set which matches required length is extracted.
Python3
# Python3 code to demonstrate working of# Most common elements set# Using loop + intersection()# initializing listtest_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}]# printing original listprint("The original list is : " + str(test_list))# initializing arg_setarg_set = {9, 6, 5, 3}# getting maximum length max_len = max(len(sub.intersection(arg_set)) for sub in test_list)# getting element matching lengthres = [sub for sub in test_list if len(sub.intersection(arg_set)) == max_len][0]# printing resultprint("Set intersection : " + str(res)) |
Output:
The original list is : [{2, 3, 4, 5}, {8, 2, 4, 7}, {1, 2, 3, 4}, {9, 3, 5, 7}]
Max Set intersection : {9, 3, 5, 7}
Method 3: Using Reduce and Lambda Function
Step-by-Step algorithm :
- Initialize res to the first set in test_list
- Use reduce() and a lambda function to compare each set in test_list with arg_set based on the number of elements they have in common:
a. If the current set in test_list has more elements in common with arg_set than res, set res to the current set
b. Otherwise, keep res as is - Return res
Python3
from functools import reduce# initializing listtest_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}]# printing original listprint("The original list is : " + str(test_list))# initializing arg_setarg_set = {9, 6, 5, 3}# using reduce() + lambda to get max common elements setres = reduce(lambda x, y: x if len(x.intersection(arg_set)) > len(y.intersection(arg_set)) else y, test_list)# printing resultprint("Max Set intersection : " + str(res)) |
The original list is : [{2, 3, 4, 5}, {8, 2, 4, 7}, {1, 2, 3, 4}, {9, 3, 5, 7}]
Max Set intersection : {9, 3, 5, 7}
Time complexity: O(n), where n is the number of sets
Auxiliary Space: O(1)
Method 4: Using the heapq module to find the set with the maximum number of common elements
- Initialize a list common_list with the result of mapping each set in test_list to its intersection with arg_set using the map() function and the set.intersection() method.
- Initialize a list heap with the negative length of each set in common_list (negated to create a min-heap).
- Use the heapq.nlargest() function to find the set in test_list with the maximum number of elements in common_list.
- Return the set with the maximum number of common elements.
Python3
import heapq# initializing listtest_list = [{4, 3, 5, 2}, {8, 4, 7, 2}, {1, 2, 3, 4}, {9, 5, 3, 7}]# initializing arg_setarg_set = {9, 6, 5, 3}# using map() to get common elementscommon_list = list(map(lambda s: s.intersection(arg_set), test_list))# using heapq.nlargest() to get set with max common elementsmax_common_set = heapq.nlargest(1, test_list, key=lambda s: len(s.intersection(arg_set)))[0]# printing resultprint("Max Set intersection : " + str(max_common_set)) |
Max Set intersection : {9, 3, 5, 7}
Time complexity: O(n log n), where n is the number of sets in test_list, due to the use of the heapq.nlargest() function.
Auxiliary space: O(n), to store the common_list and heap lists.
