Python | Group list elements based on frequency

Given a list of elements, write a Python program to group list elements and their respective frequency within a tuple. 

Examples:

Input : [1, 3, 4, 4, 1, 5, 3, 1]
Output : [(1, 3), (3, 2), (4, 2), (5, 1)]

Input : ['x', 'a', 'x', 'y', 'a', 'x']
Output : [('x', 3), ('a', 2), ('y', 1)]

Method #1: List comprehension We can use list comprehension to form tuples of each element and the count of its occurrence and store it in ‘res’, but that will contain the duplicate first element. Thus, to remove the duplicate first element, we use OrderedDict(res).items(). 

[(1, 3), (3, 2), (4, 2), (5, 1)]

Time Complexity: O(n^2) as we are using two for loops to count the frequency of each element in the list and store it in a new list.
Auxiliary Space: O(n) as we are using an additional list to store the frequency of each element in the original list.

Method #2: Using collections.Counter() collections.Counter() provides two direct methods keys() and values() that provides the elements and its occurrences. At last, zip them together using Python zip() method. 

[(1, 3), (3, 2), (4, 2), (5, 1)]

The time complexity of the group_list() function is O(n), where n is the length of the input list.

The space complexity of the group_list() function is O(k), where k is the number of unique elements in the input list. 

Method #3: Using itertools.groupby()

This method uses the itertools.groupby() function to group the elements of the list by their value, and then uses a list comprehension to create a list of tuples containing each element and the length of its group (i.e. its frequency).

[(1, 3), (3, 2), (4, 2), (5, 1)]

Time complexity: O(nlogn)
Auxiliary Space: O(n)

Method #4: Using dictionary

We can also solve the problem by using a dictionary to keep track of the frequency of each element. We can iterate through the list and for each element, we check if it’s already in the dictionary. If it is, we increment its value by 1, otherwise, we add it to the dictionary with a value of 1. Finally, we can create a list of tuples from the dictionary’s items.

Step-by-step approach:

• Initialize an empty dictionary called freq_dict to keep track of the frequency of each element in the list.
• Iterate through the elements in the list
• For each element, check if it’s already in freq_dict.
• If it is, increment its value by 1.
• If it’s not, add it to the dictionary with a value of 1.
• Create a list of tuples from the dictionary’s items using the items() method.
• Sort the list of tuples in descending order based on the frequency of the elements.
• Return the sorted list of tuples.

Below is the implementation of the above approach:

[(1, 3), (3, 2), (4, 2), (5, 1)]

Time complexity: O(n*logn) due to the sorting step. The dictionary operations take O(1) time.
Auxiliary space: O(n) to store the dictionary.

Method #5: Using set() and count()

Steps:

1. Define a function called “group_list” that takes a list “lst” as input.
2. Create an empty list called “result” to store the grouped elements.
3. Create a set of unique elements in the input list “lst” using the “set” function.
4. Use a for loop to iterate over each element in the set.
5. Use the “count” method to count the number of occurrences of the current element in the input list “lst”.
6. Append a tuple of the current element and its frequency to the “result” list using the “append” method.
7. Once all the elements in the set have been processed, return the “result” list.
8. Define the input list “lst”.
9. Call the “group_list” function with the “lst” argument and store the result in “grouped_list”.
10. Print the “grouped_list” using the “print” statement.

[(1, 3), (3, 2), (4, 2), (5, 1)]

Time complexity: O(n^2) where n is the length of the input list “lst” as we need to count the occurrences of each unique element in the list.

Auxiliary space: O(n) as we need to store the frequencies of all unique elements in the input list in the result list.