Given tuple list, extract the frequency of unique tuples in list order irrespective.
Input : test_list = [(3, 4), (1, 2), (4, 3), (3, 4)] Output : 2 Explanation : (3, 4), (4, 3), (3, 4) makes 1 and (1, 2) is 2nd unique element.
Input : test_list = [(3, 7), (1, 2), (4, 3), (5, 6)] Output : 4 Explanation : All are different in any order.
Method #1 : Using tuple() + generator expression + sorted() + len()
The combination of above functions can be used to solve this problem. In this, we perform the task of sorting using sorted(), to remove order constraints. The len() is used to compute size.
Python3
# Python3 code to demonstrate working of# Unique Tuple Frequency [ Order Irrespective ]# Using tuple() + list comprehension + sorted() + len()# initializing liststest_list = [(3, 4), (1, 2), (4, 3), (5, 6)]# printing original listprint("The original list is : " + str(test_list))# Using tuple() + list comprehension + sorted() + len()# Size computed after conversion to setres = len(list(set(tuple(sorted(sub)) for sub in test_list)))# printing resultprint("Unique tuples Frequency : " + str(res)) |
The original list is : [(3, 4), (1, 2), (4, 3), (5, 6)] Unique tuples Frequency : 3
Time Complexity: O(nlogn) where n is the number of elements in the list
Auxiliary Space: O(n), where n is the number of elements in the list
Method #2: Using map() + sorted() + tuple() + set() + len()
The combination of the above functions can be used to solve this problem. In this, we perform the task of extending sorting logic and tuple conversion using map(), set() is used to eliminate duplicates and len() is used to find the length of the container.
Python3
# Python3 code to demonstrate working of# Unique Tuple Frequency [ Order Irrespective ]# Using map() + sorted() + tuple() + set() + len()# initializing liststest_list = [(3, 4), (1, 2), (4, 3), (5, 6)]# printing original listprint("The original list is : " + str(test_list))# Using map() + sorted() + tuple() + set() + len()# inner map used to perform sort and outer sort to# convert again in tuple formatres = len(list(set(map(tuple, map(sorted, test_list)))))# printing resultprint("Unique tuples Frequency : " + str(res)) |
The original list is : [(3, 4), (1, 2), (4, 3), (5, 6)] Unique tuples Frequency : 3
Method#3: Using Recursive method.
This method works by recursively calling itself with the remaining elements of the input list after the first element is removed. It then checks if the first element is unique by comparing it to the sorted version of each of the remaining elements. If the first element is unique, it adds 1 to the frequency returned by the recursive call. If it is not unique, it simply returns the frequency returned by the recursive call. The base case is when the input list is empty, in which case the frequency is 0.
Python3
def unique_tuple_frequency(test_list): # base case if len(test_list) == 0: return 0 # recursive call rest_freq = unique_tuple_frequency(test_list[1:]) # check if the first element is unique for t in test_list[1:]: if sorted(test_list[0]) == sorted(t): return rest_freq # if the first element is unique, add 1 to the frequency return rest_freq + 1# initializing liststest_list = [(3, 4), (1, 2), (4, 3), (5, 6)]# printing original listprint("The original list is :" + str(test_list))# Using map() + sorted() + tuple() + set() + len()# inner map used to perform sort and outer sort to# convert again in tuple formatres = unique_tuple_frequency(test_list)# printing resultprint("Unique tuples Frequency : " + str(res)) |
The original list is :[(3, 4), (1, 2), (4, 3), (5, 6)] Unique tuples Frequency : 3
Time Complexity: O(N * MlogM)
Sorting each tuple: O(MlogM) where M is the size of the tuple.
Comparing each tuple to the first tuple: O(N * M) where N is the length of the input list and M is the size of the tuple.
Overall time complexity: O(N * MlogM)
Auxiliary Space: O(N * M)
Recursive call stack: O(N)
Creating a new list of remaining elements for each recursive call: O(N * M)
Method #4: Using dictionary and loop
Steps:
- Initialize an empty dictionary “freq_dict” to store the frequency of each unique tuple.
- Loop through each tuple in the input list “test_list”.
- Sort the tuple using sorted() and convert it to a tuple again using tuple(). This will give us a sorted version of the tuple, which we can use to check if it is unique.
- Check if the sorted tuple exists as a key in the “freq_dict”.
- If it does, increment the value of the corresponding key in “freq_dict”.
- If it does not, add the sorted tuple as a key to “freq_dict” with a value of 1.
- Finally, return the length of “freq_dict”, which will give us the number of unique tuples in “test_list”.
Python3
def unique_tuple_frequency(test_list): freq_dict = {} for tup in test_list: sorted_tup = tuple(sorted(tup)) if sorted_tup in freq_dict: freq_dict[sorted_tup] += 1 else: freq_dict[sorted_tup] = 1 return len(freq_dict)# Initializing liststest_list = [(3, 4), (1, 2), (4, 3), (5, 6)]# Printing original listprint("The original list is :" + str(test_list))# Using dictionary and loopres = unique_tuple_frequency(test_list)# Printing resultprint("Unique tuples Frequency : " + str(res)) |
The original list is :[(3, 4), (1, 2), (4, 3), (5, 6)] Unique tuples Frequency : 3
Time complexity: O(nlogn), where n is the length of the input list “test_list”.
Auxiliary space: O(n), where n is the length of the input list “test_list”.
