Given tuple list, assign frequency to each tuple in list.
Input : test_list = [(6, 5, 8), (2, 7), (6, 5, 8), (9, ), (2, 7)]
Output : [(6, 5, 8, 2), (2, 7, 2), (9, 1)]
Explanation : (2, 7) occurs 2 times, hence 2 is append in tuple.
Input : test_list = [(2, 7), (2, 7), (6, 5, 8), (9, ), (2, 7)]
Output : [(6, 5, 8, 1), (2, 7, 3), (9, 1)]
Explanation : (2, 7) occurs 3 times, hence 3 is append in tuple.
Method #1 : Using Counter() + items() + * operator + list comprehension
In this, we extract the frequency using Counter(), fetch frequency numbers using items(), * operator is used to unpack elements and list comprehension is used to assign this to all elements in tuple list.
Python3
# Python3 code to demonstrate working of # Assign Frequency to Tuples# Using Counter() + items() + * operator + list comprehensionfrom collections import Counter# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# one-liner to solve problem# assign Frequency as last element of tupleres = [(*key, val) for key, val in Counter(test_list).items()]# printing resultsprint("Frequency Tuple list : " + str(res)) |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)] Frequency Tuple list : [(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Method #2 : Using most_common() + Counter() + * operator + list comprehension
This is similar to the above method, just most_common() performs sort operation on list, which is not necessary.
Python3
# Python3 code to demonstrate working of # Assign Frequency to Tuples# Using most_common() + Counter() + * operator + list comprehensionfrom collections import Counter# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# most_common performs sort on arg. list# assign Frequency as last element of tupleres = [(*key, val) for key, val in Counter(test_list).most_common()]# printing resultsprint("Frequency Tuple list : " + str(res)) |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)] Frequency Tuple list : [(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Method #3 : Using count(),list(),tuple() methods
Python3
# Python3 code to demonstrate working of# Assign Frequency to Tuples# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# one-liner to solve problem# assign Frequency as last element of tupleres=[]for i in test_list: if i not in res: res.append(i)res1=[]for i in res: x=list(i) x.append(test_list.count(i)) p=tuple(x) res1.append(p)# printing resultsprint("Frequency Tuple list : " + str(res1)) |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9,), (2, 7)] Frequency Tuple list : [(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Method #4 : Using operator.countOf(),list(),tuple() methods
Python3
# Python3 code to demonstrate working of# Assign Frequency to Tuplesimport operator as op# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# one-liner to solve problem# assign Frequency as last element of tupleres=[]for i in test_list: if i not in res: res.append(i)res1=[]for i in res: x=list(i) x.append(op.countOf(test_list,i)) p=tuple(x) res1.append(p)# printing resultsprint("Frequency Tuple list : " + str(res1)) |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9,), (2, 7)] Frequency Tuple list : [(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Time Complexity: O(N*N), where n is the length of the given tuple
Auxiliary Space: O(N*N)
METHOD 5:Using dictionary and list comprehension: The method returns the value for a key if it exists in the dictionary, otherwise it returns a default value of 0. This allows us to simplify the if-else statement in the for a loop. The rest of the solution is the same as before, creating a list of tuples using list comprehension.
- Create an empty dictionary to store the frequencies of each tuple.
- Iterate over each tuple in the given list and add it to the dictionary if it doesn’t exist, with a frequency of 1. If the tuple already exists, increment its frequency by 1.
- Use a list comprehension to create a new list of tuples with the original tuples and their frequencies.
Python3
# Python program for the above approach# Function to assign frequencydef assign_frequency(lst): freq_dict = {} for tup in lst: if tup in freq_dict: freq_dict[tup] += 1 else: freq_dict[tup] = 1 return [(key + (value,)) for key, value in freq_dict.items()]# Driver Codelst = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]print(assign_frequency(lst)) |
[(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Time Complexity: O(n) where n is the number of tuples in the list.
Space Complexity: O(n) since the dictionary stores the frequencies of each tuple.
METHOD 6:Using reduce():
Algorithm:
- Import Counter and reduce from their respective modules.
- Initialize the original list test_list.
- Print the original list.
- Use reduce to merge all the tuples in the list into a single Counter object that counts the frequency of each tuple.
- Create a list of tuples by iterating over the Counter object, unpacking each tuple into the tuple elements and frequency.
- Sort the list of tuples in descending order of frequency.
- Print the final list.
Python3
from collections import Counterfrom functools import reduce# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# using reduce to merge tuples and sum their countsres = reduce(lambda x, y: x + y, [Counter([t]) for t in test_list])# creating list of tuples with frequency as last elementres = [(*key, val) for key, val in res.items()]# sorting the list in descending order of frequencyres.sort(key=lambda x: x[-1], reverse=True)# printing resultsprint("Frequency Tuple list : " + str(res))#This code is contributed by Rayudu. |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9,), (2, 7)] Frequency Tuple list : [(6, 5, 8, 3), (2, 7, 2), (9, 1)]
Time complexity: O(n log n), where n is the length of the original list. This is because sorting the list of tuples takes O(n log n) time.
Space complexity: O(n), where n is the length of the original list. This is because we create a new list of tuples with the same length as the original list. The Counter object also takes O(n) space.
METHOD 7:Using groupby():
Algorithm:
- Create an empty dictionary, freq_dict.
- For each element in the list, do the following:
a. Check if the element is already in the dictionary.
b. If it is not in the dictionary, add it with a value of 1.
c. If it is in the dictionary, increment its value by 1. - Create an empty list, freq_list.
- For each key-value pair in the dictionary, create a tuple (key, value) and append it to the freq_list.
- Sort the freq_list in ascending order based on the second element (frequency).
- Return the freq_list.
Python3
import itertools# initializing listtest_list = [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9, ), (2, 7)]# printing original listprint("The original list is : " + str(test_list))# use groupby to get unique rows and their countsres = []for row, group in itertools.groupby(sorted(test_list)): count = sum(1 for _ in group) res.append(row + (count,))# print resultprint("Frequency Tuple list : " + str(res))#This code is contributed by Vinay pinjala. |
The original list is : [(6, 5, 8), (2, 7), (6, 5, 8), (6, 5, 8), (9,), (2, 7)] Frequency Tuple list : [(2, 7, 2), (6, 5, 8, 3), (9, 1)]
Time complexity:
The time complexity of this algorithm is O(n log n), where n is the length of the input list. This is because the algorithm involves iterating through the input list once (O(n)), adding and updating dictionary elements (which has an average case time complexity of O(1)), creating a new list of tuples (O(n)), and sorting that list using Python’s built-in sorted function (which has a time complexity of O(n log n)).
Auxiliary Space:
The space complexity of this algorithm is O(n), where n is the length of the input list. This is because the algorithm creates a dictionary with up to n unique elements, a list with n elements, and several temporary variables (which have a constant space complexity).
