Python | Remove duplicate lists in tuples (Preserving Order)
Sometimes, while working with records, we can have a problem in which we need to remove duplicate records. This kind of problem is common in web development domain. Let’s discuss certain ways in which this task can be performed.
Method #1 : Using list comprehension + set()
In this method, we test for each list as it appears and add it to set so that it’s repeated occurrence can be avoided and then this is added to newly maintained unique tuple, removing duplicates.
Python3
# Python3 code to demonstrate working of # Remove duplicate lists in tuples(Preserving Order) # Using list comprehension + set() # Initializing tuple test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) # printing original tuple print ( "The original tuple is : " + str (test_tup)) # Remove duplicate lists in tuples(Preserving Order) # Using list comprehension + set() temp = set () res = [ele for ele in test_tup if not ( tuple (ele) in temp or temp.add( tuple (ele)))] # printing result print ( "The unique lists tuple is : " + str (res)) |
The original tuple is : ([4, 7, 8], [1, 2, 3], [4, 7, 8], [9, 10, 11], [1, 2, 3]) The unique lists tuple is : [[4, 7, 8], [1, 2, 3], [9, 10, 11]]
Time complexity: O(n)
Auxiliary Space: O(n)
Method #2 : Using OrderedDict() + tuple()
The combination of above functions can also be used to perform this particular task. In this, we convert the tuple to OrderedDict(), which automatically removes the duplicate elements and then construct a new tuple list using tuple().
Python3
# Python3 code to demonstrate working of # Remove duplicate lists in tuples(Preserving Order) # Using OrderedDict() + tuple() from collections import OrderedDict # Initializing tuple test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) # printing original tuple print ( "The original tuple is : " + str (test_tup)) # Remove duplicate lists in tuples(Preserving Order) # Using OrderedDict() + tuple() res = list (OrderedDict(( tuple (x), x) for x in test_tup).values()) # printing result print ( "The unique lists tuple is : " + str (res)) |
The original tuple is : ([4, 7, 8], [1, 2, 3], [4, 7, 8], [9, 10, 11], [1, 2, 3]) The unique lists tuple is : [[4, 7, 8], [1, 2, 3], [9, 10, 11]]
Method #3: Using recursive method.
Python3
# Python3 code to demonstrate working of # Remove duplicate lists in tuples(Preserving Order) # Using Recursive method # Recursive function to remove duplicate lists in a tuple def remove_duplicates(tup, result, seen): # Base case: if the tuple is empty, return the result if not tup: return result # If the current list is not in the "seen" set, append it to the result # and add it to the "seen" set if tuple (tup[ 0 ]) not in seen: result.append(tup[ 0 ]) seen.add( tuple (tup[ 0 ])) # Recursively call the function with the rest of the tuple return remove_duplicates(tup[ 1 :], result, seen) # Initialize the tuple test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) # Call the function with an empty result list and an empty set result = [] seen = set () res = remove_duplicates(test_tup, result, seen) # printing original tuple print ( "The original tuple is : " + str (test_tup)) # printing result print ( "The unique lists tuple is : " + str (res)) #this code contributed by tvsk |
The original tuple is : ([4, 7, 8], [1, 2, 3], [4, 7, 8], [9, 10, 11], [1, 2, 3]) The unique lists tuple is : [[4, 7, 8], [1, 2, 3], [9, 10, 11]]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #4:Using a loop and a set:
Algorithm:
1.Create an empty list called “result” and an empty set called “seen”.
2.For each sublist in the input tuple:
a. Convert the sublist to a tuple called “t”.
b. If “t” is not in the “seen” set, append the original sublist to the “result” list and add “t” to the “seen” set.
3.Convert the “result” list to a tuple and return it.
Python3
def remove_duplicates(tup): result = [] seen = set () for sublist in tup: t = tuple (sublist) if t not in seen: result.append(sublist) seen.add(t) return tuple (result) # Example usage test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) unique_tup = remove_duplicates(test_tup) print ( "Original tuple:" , test_tup) print ( "Tuple with duplicate lists removed:" , unique_tup) #This code is contributed by Jyothi pinjala |
Original tuple: ([4, 7, 8], [1, 2, 3], [4, 7, 8], [9, 10, 11], [1, 2, 3]) Tuple with duplicate lists removed: ([4, 7, 8], [1, 2, 3], [9, 10, 11])
Time complexity: O(n*m) where n is the number of sublists in the input tuple and m is the length of the largest sublist. This is because we need to iterate over each sublist and create a tuple from it, and checking membership in a set takes constant time on average.
Auxiliary Space: O(n*m) because we need to store the input tuple, the output list, and the set of seen tuples. In the worst case where all sublists are unique, the size of the output list will be equal to the size of the input tuple, so the space complexity will be proportional to the size of the input tuple.
Method #5: Using loop and if-else statement
Algorithm:
- Initialize an empty list res to store unique lists.
- Loop through each list i in the given tuple test_tup.
- If the list i is not already in the res list, then append i to the res list.
- Return the res list as the result.
Python3
test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) res = [] for i in test_tup: if i not in res: res.append(i) print ( "The unique lists tuple is : " + str (res)) #This code is contributed by Vinay Pinjala. |
The unique lists tuple is : [[4, 7, 8], [1, 2, 3], [9, 10, 11]]
Time Complexity:
The loop runs n times, where n is the length of the input tuple.
The list append operation and the list membership test both have O(1) time complexity on average.
Therefore, the overall time complexity of the algorithm is O(n) on average.
Auxiliary Space:
The space used by the res list is O(k), where k is the number of unique lists in the input tuple.
The space used by other variables is constant.
Therefore, the overall space complexity of the algorithm is O(k).
Method 6: Using generator function
Define a generator function that takes a tuple as input.
Initialize an empty set to store the seen tuples.
Loop through the original tuple.
Convert the current list to a tuple and check if it is already in the set.
If it is not in the set, yield the current list and add the tuple to the set.
Return the generator function.
Python3
# Python3 code to demonstrate working of # Remove duplicate lists in tuples(Preserving Order) # Using Generator function # Generator function to remove duplicate lists in a tuple def remove_duplicates(tup): seen = set () for lst in tup: tup_lst = tuple (lst) if tup_lst not in seen: yield lst seen.add(tup_lst) # Initialize the tuple test_tup = ([ 4 , 7 , 8 ], [ 1 , 2 , 3 ], [ 4 , 7 , 8 ], [ 9 , 10 , 11 ], [ 1 , 2 , 3 ]) # Call the generator function to get the unique lists tuple res = tuple (remove_duplicates(test_tup)) # printing original tuple print ( "The original tuple is : " + str (test_tup)) # printing result print ( "The unique lists tuple is : " + str (res)) |
The original tuple is : ([4, 7, 8], [1, 2, 3], [4, 7, 8], [9, 10, 11], [1, 2, 3]) The unique lists tuple is : ([4, 7, 8], [1, 2, 3], [9, 10, 11])
This method has a time complexity of O(n), where n is the length of the input tuple, since we only loop through the tuple once.
This method has an auxiliary space complexity of O(n), where n is the length of the input tuple, since we need to store the unique tuples in a set.