Given a nested list, the task is to remove all duplicates and permutations in that nested list.
Input: [[-11, 0, 11], [-11, 11, 0], [-11, 0, 11],
[-11, 2, -11], [-11, 2, -11], [-11, -11, 2]]
Output: {(-11, 0, 11), (-11, -11, 2)}
Input: [[-1, 5, 3], [3, 5, 0], [-1, 5, 3],
[1, 3, 5], [-1, 3, 5], [5, -1, 3]]
Output: {(1, 3, 5), (0, 3, 5), (-1, 3, 5)}
Code #1: Using Map
Python3
# Python code to remove all duplicates# and permutations in nested list#InitialisationlistOfPermut = [[-11, 0, 11], [-11, 11, 0], [-11, 0, 11], [-11, 2, -11], [-11, -11, 2], [2, -11, -11]]# Sorting tuple then removingoutput = set(map(lambda x: tuple(sorted(x)),listOfPermut))# printing outputprint(output) |
{(-11, 0, 11), (-11, -11, 2)}
Time Complexity: O(n), where n is the length of the list
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list
Code #2:
Python3
# Python code to remove all duplicates# and permutations in nested list# Initialisationinput = [[-11, 0, 11], [-11, 11, 0], [-11, 2, -11], [-11, -11, 2], [2, -11, -11]]# Sorting tuple then removingoutput = set(tuple(sorted(x)) for x in input)# printing outputprint(output) |
{(-11, 0, 11), (-11, -11, 2)}
Code #3: Using sort() and not in operator
Python3
# Python code to remove all duplicates# and permutations in nested list# Initialisationinput = [[-11, 0, 11], [-11, 11, 0], [-11, 2, -11], [-11, -11, 2], [2, -11, -11]]# Sorting tuple then removingres = []for i in input: i.sort() res.append(i)output = []for i in res: if i not in output: output.append(i)output = list(map(tuple, output))print(tuple(output)) |
((-11, 0, 11), (-11, -11, 2))
Code #4: Using operator.countOf() method
Python3
# Python code to remove all duplicates# and permutations in nested listimport operator as op# Initialisationinput = [[-11, 0, 11], [-11, 11, 0], [-11, 2, -11], [-11, -11, 2], [2, -11, -11]]# Sorting tuple then removingres = []for i in input: i.sort() res.append(i)output = []for i in res: if op.countOf(output, i) == 0: output.append(i)output = list(map(tuple, output))print(tuple(output)) |
((-11, 0, 11), (-11, -11, 2))
Time Complexity: O(N*N)
Auxiliary Space: O(N*N)
Approach#4:Using dictionary
This approach uses set comprehension and dictionary to remove duplicates and count frequency respectively. It sorts each sublist to account for permutations and converts them into tuples to make them hashable.
Algorithm
1. Create an empty set called tuple_set.
2. Iterate through each nested list in the given nested list and sort it.
3. Convert each sorted nested list into a tuple and add it to the tuple_set.
4. Create an empty dictionary called freq_dict.
5. Iterate through each tuple in the tuple_set and add it to the freq_dict with its frequency as the value.
6. Find the maximum frequency value in the freq_dict.
7. Create an empty set called unique_tuples.
8. Iterate through each key-value pair in the freq_dict and check if the frequency is equal to the maximum frequency.
9. If it is, convert the key back into a tuple, sort it, and add it to the unique_tuples set.
10. Return the unique_tuples set.
Python3
def remove_duplicates(nested_list): tuple_set = {tuple(sorted(lst)) for lst in nested_list} freq_dict = {} for t in tuple_set: if t not in freq_dict: freq_dict[t] = 1 else: freq_dict[t] += 1 max_freq = max(freq_dict.values()) unique_tuples = {tuple(sorted(k)) for k, v in freq_dict.items() if v == max_freq} return unique_tuplesnested_list = [[-11, 0, 11], [-11, 11, 0], [-11, 2, -11], [-11, -11, 2], [2, -11, -11]]print(remove_duplicates(nested_list)) |
{(-11, 0, 11), (-11, -11, 2)}
Time complexity: O(NMlogM), where N is the number of nested lists and M is the length of the longest nested list. Sorting each nested list takes O(MlogM) time, and iterating through each nested list takes O(NM) time.
Space complexity: O(N*M), as we are creating a new set and dictionary to store the unique tuples and their frequencies.