Given a list of lists, the task is to write a python program that can convert each sublist to a set and combine to sublists into one set if they have a common element. The output printed will be a list of sets.
Input : test_list = [[15, 14, 12, 18], [9, 5, 2, 1], [4, 3, 2, 1], [19, 11, 13, 12]]
Output : [{11, 12, 13, 14, 15, 18, 19}, {1, 2, 3, 4, 5, 9}]
Explanation : List 1 and list 4 had 12 in common, hence all got merged to one.
Input : test_list = [[15, 14, 12, 18], [9, 5, 2, 1], [4, 3, 2, 1], [19, 11, 13, 22]]
Output : [{18, 12, 14, 15}, {1, 2, 3, 4, 5, 9}, {11, 19, 13, 22}]
Explanation : List 2 and list 3 had 1, 2 in common, hence all got merged to one.
Method : Using recursion and union()
In this, we perform the task of getting all containers having like elements using union(), depending upon conditions. Recursion is used to perform similar task to most lists required.
Example:
Python3
# utility functiondef common_set(test_set): for idx, val in enumerate(test_set): for j, k in enumerate(test_set[idx + 1:], idx + 1): # getting union by conditions if val & k: test_set[idx] = val.union(test_set.pop(j)) return common_set(test_set) return test_set# utility function# initializing liststest_list = [[15, 14, 12, 18], [9, 5, 2, 1], [4, 3, 2, 1], [19, 11, 13, 12]]# printing original listprint("The original list is : " + str(test_list))test_set = list(map(set, test_list))# calling recursive functionres = common_set(test_set)# printing resultprint("Common element groups : " + str(res)) |
Output:
The original list is : [[15, 14, 12, 18], [9, 5, 2, 1], [4, 3, 2, 1], [19, 11, 13, 12]]
Common element groups : [{11, 12, 13, 14, 15, 18, 19}, {1, 2, 3, 4, 5, 9}]
Time Complexity: O(n*n)
Auxiliary Space: O(n)
Approach#2: Using set intersection
The approach used in this code is to iterate over each list in the input list, convert it to a set, and then find all other lists that have common elements with it. Then, it merges all the common lists into one set and removes them from the input list. This process is repeated until there are no more lists left in the input list.
- Create an empty list result to store the final sets.
- While the input list test_list is not empty:
- Remove the first list from test_list and convert it to a set last.
- Find all other lists in test_list that have common elements with last.
- Merge all common lists into one set and remove them from test_list.
- Add the merged set to the result.
- Return result.
Python3
# Python program for the above approach# Function to reverse the list into setdef convert_list_to_set(test_list): # Create an empty list to store the result result = [] # Iterate over each list in the input list while test_list: # Remove the first list from the input # list and convert it to a set lst = set(test_list.pop(0)) # Find all other lists that have # common elements with the first list common_lists = [l for l in test_list if lst.intersection(set(l))] # Merge all common lists into one set # and remove them from the input list for common_lst in common_lists: lst |= set(common_lst) test_list.remove(common_lst) # Add the merged set to the result result.append(lst) return result# Driver Codetest_list = [[15, 14, 12, 18], [9, 5, 2, 1], [4, 3, 2, 1], [19, 11, 13, 12]]print(convert_list_to_set(test_list)) |
[{11, 12, 13, 14, 15, 18, 19}, {1, 2, 3, 4, 5, 9}]
Time complexity: O(n^2), where n is the length of the input list test_list. This is because we are iterating over each list in test_list and then iterating over the remaining lists to find the common elements.
Space complexity: O(n^2), where n is the length of the input list test_list. This is because we are creating sets for each list in test_list, and we are also creating a list of common lists for each lst in test_list.
