Union of a list means, we must take all the elements from list A and list B (there can be more than two lists) and put them inside a single new list. There are various orders in which we can combine the lists. For e.g., we can maintain the repetition and order or remove the repeated elements in the final list and so on.
Examples:
Maintained repetition only
Input :
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
Output :
[23, 15, 2, 14, 14, 16, 20, 52, 2, 48,
15, 12, 26, 32, 47, 54]
Maintained repetition and order
Input :
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
Output :
[2, 2, 12, 14, 14, 15, 15, 16, 20, 23,
26, 32, 47, 48, 52, 54]
Without repetition
Input :
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
Output :
[32, 2, 12, 14, 15, 16, 48, 47, 20, 52, 54, 23, 26]
Union of three lists
Input :
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
lst3 = [4, 78, 5, 6, 9, 25, 64, 32, 59]
Output :
[32, 64, 2, 4, 5, 6, 9, 12, 14, 15, 16,
48, 47, 78, 20, 52, 54, 23, 25, 26, 59]
Maintaining Repetition
We can simply use the plus “+” operator inorder to combine two list into one. This will reflect the repetition.
Python3
def Union(lst1, lst2):
final_list = lst1 + lst2
return final_list
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
print(Union(lst1, lst2))
|
Output:
[23, 15, 2, 14, 14, 16, 20, 52, 2, 48, 15,
12, 26, 32, 47, 54]
Time complexity: O(n), where n is the length of the longest list.
Auxiliary space complexity: O(n), where n is the total number of elements in both lists.
Maintaining both Repetition and Order
To maintain the order of appearance in the new list we need to use the sorted() function, passing the addition of two lists(plus operated, as in the previous problem) as parameters.
Python3
def Union(lst1, lst2):
final_list = sorted(lst1 + lst2)
return final_list
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
print(Union(lst1, lst2))
|
Output:
[2, 2, 12, 14, 14, 15, 15, 16, 20, 23, 26, 32, 47, 48, 52, 54]
The time complexity of the Union function is O(n log n), where n is the total number of elements in both lists.
The space complexity of the Union function is O(n), where n is the total number of elements in both lists.
Without Repetition
To get rid of all the repetitive elements from the initial list, we use the set() function on both the lists, individually. Then we add them using the “+” operator and pass as a new list.
Python3
def Union(lst1, lst2):
final_list = list(set(lst1) | set(lst2))
return final_list
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
print(Union(lst1, lst2))
|
Output:
[32, 2, 12, 14, 15, 16, 48, 47, 20,
52, 54, 23, 26]
More than two lists
We can also make an union of more than two lists. This can be done efficiently by using both the set() and union() function, simultaneously, as shown in the below example. This also takes care of the repetition and prevents them.
Python3
def Union(lst1, lst2, lst3):
final_list = list(set().union(lst1, lst2, lst3))
return final_list
lst1 = [23, 15, 2, 14, 14, 16, 20 ,52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
lst3 = [4, 78, 5, 6, 9, 25, 64, 32, 59]
print(Union(lst1, lst2, lst3))
|
Output:
[32, 64, 2, 4, 5, 6, 9, 12, 14, 15, 16,
48, 47, 78, 20, 52, 54, 23, 25, 26, 59]
Approach : Using extend() method
Step-by-step approach:
- First, import the “collections” module in the Python program.
- Define two lists: lst1 and lst2 which contain some integer values.
- Use the extend() method to append all the elements of lst2 to lst1. Now, lst1 contains all the elements of both lst1 and lst2.
- Use the print() function to display the combined list, lst1, which maintains the repetition of elements.
- Use the set() function to create a set from lst1, which will not maintain the repetition of elements or the order of elements.
- Use the list() function to convert the resulting set back into a list.
- Use the print() function to display the new list, x, which does not maintain repetition or order.
Below is the implementation of the above approach:
Python3
lst1 = [23, 15, 2, 14, 14, 16, 20, 52]
lst2 = [2, 48, 15, 12, 26, 32, 47, 54]
lst1.extend(lst2)
print("Maintaining repetition "+str(lst1))
x = list(set(lst1))
print("Not maintaining repetition "+str(x))
|
Output
Maintaining repetition [23, 15, 2, 14, 14, 16, 20, 52, 2, 48, 15, 12, 26, 32, 47, 54]
Not maintaining repetition [32, 2, 12, 14, 15, 16, 48, 47, 20, 52, 54, 23, 26]
Approach : Using itertools
The itertools module has functions for working with iterable data structures in Python. One of its functions is chain() function which can be used to concatenate two or more lists together.
Algorithm:
- Import the itertools module.
- Use the chain() function from the itertools module to concatenate two or more lists into one list.
- Use the set() function to remove duplicates and convert the concatenated list to a set
- Convert the set back to a list and return it as the final union
Return the concatenated list.
Example code to concatenate two lists using chain():
Python3
import itertools
def union_lists(*lists):
concatenated_list = list(itertools.chain(*lists))
unique_set = set(concatenated_list)
final_union = list(unique_set)
return final_union
list1 = [23, 15, 2, 14, 14, 16, 20 ,52]
list2 = [2, 48, 15, 12, 26, 32, 47, 54]
list3 = [4, 78, 5, 6, 9, 25, 64, 32, 59]
print(union_lists(list1, list2, list3))
|
Output
[2, 4, 5, 6, 9, 12, 14, 15, 16, 20, 23, 25, 26, 32, 47, 48, 52, 54, 59, 64, 78]
The time complexity of the union_lists() function is O(n), where n is the total number of elements in all input lists.
The auxiliary space of the union_lists() function is O(n), where n is the total number of elements in all input lists, due to creating a concatenated list and a set of unique elements.
Please Login to comment...