Symmetric Differences among groups of sets are elements that belong to any one of the sets but are not present in any other set. Given a list of sets and the task is to write a Python program to get the symmetric difference of the same.
Input : test_list = [{5, 3, 2, 6, 1}, {7, 5, 3, 8, 2}, {9, 3}, {0, 3, 6, 7}]
Output : {8, 1, 9, 0}
Explanation : 8, 1, 9, 0 occur just 1 time over whole container.
Input : test_list = [{5, 3, 2, 6, 1}, {7, 5, 3, 8, 2}, {9, 3}]
Output : {8, 1, 9}
Explanation : 8, 1, 9 occur just 1 time over whole container.
Method #1: Using Counter() + chain.from_iterable()
This method is used to check for all elements that have 1 as frequency overall sets by flattening. Counter() extracts frequencies and then all elements with count 1 can be extracted.
Python3
# Python3 code to demonstrate working of# Symmetric Difference of Multiple sets# Using Counter() + chain.from_iterable() from collections import Counterfrom itertools import chain# initializing listtest_list = [{5, 3, 2, 6, 1}, {7, 5, 3, 8, 2}, {9, 3}, {0, 3, 6, 7}] # printing original listprint("The original list is : " + str(test_list))# getting frequencies using Counter()# from_iterable() flattens the list freq = Counter(chain.from_iterable(test_list))# getting frequency count 1 res = {idx for idx in freq if freq[idx] == 1}# printing resultprint("Symmetric difference of multiple list : " + str(res)) |
Output:
The original list is : [{1, 2, 3, 5, 6}, {2, 3, 5, 7, 8}, {9, 3}, {0, 3, 6, 7}]
Symmetric difference of multiple list : {8, 1, 9, 0}
Method #2 : Using Counter() + chain.from_iterable() + items()
Similar to above method, only difference being its performed in single step by extracting keys and values using items().
Python3
# Python3 code to demonstrate working of# Symmetric Difference of Multiple sets# Using Counter() + chain.from_iterable() + items()from collections import Counterfrom itertools import chain# initializing listtest_list = [{5, 3, 2, 6, 1}, {7, 5, 3, 8, 2}, {9, 3}, {0, 3, 6, 7}] # printing original listprint("The original list is : " + str(test_list))# clubbing operations using items() to get items res = {key for key, val in Counter(chain. from_iterable(test_list)). items() if val == 1}# printing resultprint("Symmetric difference of multiple list : " + str(res)) |
Output:
The original list is : [{1, 2, 3, 5, 6}, {2, 3, 5, 7, 8}, {9, 3}, {0, 3, 6, 7}]
Symmetric difference of multiple list : {8, 1, 9, 0}
method#3: Using the reduce() function from functools
Approach
uses the reduce() function from the functools module to apply the symmetric_difference() method to all sets in the input list.
Algorithm
1. The lambda function passed to the reduce() function takes two sets as input and returns their symmetric difference.
2. The reduce() function iteratively applies the lambda function to all sets in the input list, resulting in the symmetric difference of all sets.
Python3
# Import the reduce() function from the functools modulefrom functools import reduce# Define the input list of setstest_list = [{5, 3, 2, 6, 1}, {7, 5, 3, 8, 2}, {9, 3}, {0, 3, 6, 7}]# Find the symmetric difference of all sets in the list using the reduce() functionsymmetric_difference = reduce(lambda a, b: a.symmetric_difference(b), test_list)# Print the resultprint(symmetric_difference) |
{0, 1, 8, 9}
Time complexity of O(n*log(n)) where n is the total number of elements in all sets.
Space complexity is O(n) for storing the symmetric difference set
METHOD 4:Using the ^ operator
APPROACH:
The given code finds the symmetric difference of multiple sets using a for loop to iterate over each set in the original list and performing the XOR operation with an initially empty set.
ALGORITHM:
1.Create an empty set symmetric_difference
2.For each set s in the original list:
3.Perform XOR operation between the symmetric_difference and s and store the result in symmetric_difference.
4.Print the symmetric_difference set.
Python3
original_list = [{1, 2, 3, 5, 6}, {2, 3, 5, 7, 8}, {9, 3}, {0, 3, 6, 7}]symmetric_difference = set()for s in original_list: symmetric_difference ^= sprint("Symmetric difference of multiple list:", symmetric_difference) |
Symmetric difference of multiple list: {0, 1, 8, 9}
Time Complexity:
The time complexity of this approach is O(NM), where N is the number of sets in the original list and M is the maximum size of any set in the list. In the worst-case scenario, where all sets have the same size, the time complexity is O(NM).
Space Complexity:
The space complexity of this approach is O(M), where M is the maximum size of any set in the original list. This is because the symmetric_difference set is the only data structure that is used to store the symmetric difference. The memory usage is proportional to the size of the largest set in the list.
