Given a list of repetitive elements, Write a Python program to shrink the repetition of the elements and convert the repetition into a tuple element of the list containing the repeated element and the number of times it has repeated, Thus, converting the given list into a list of tuples.
Examples
Input : [1, 1, 1, 2, 3, 3, 3, 4, 4, 4, 4] Output : [(1, 3), (2, 1), (3, 3), (4, 4)] Input : ['alice', 'alice', 'bob'] Output : [('alice', 2), ('bob', 1)] Explanation: In This, we are shrinking the given list for repeating elements in Python.
Shrink Given List for Repeating Elements using Brute Force
In Python, Brute force is a Naive approach in order to shrink the list. It takes another list say, ‘tup_list’. Initialize the index to 0 and use a loop to check how many times each unique element of the list is repeated. Once found the element and its repeat count, append it to the list in the form of a tuple.
Python3
# Python3 program to Shrink list # for repeating elementsdef shrinkList(lst): tup_list = [] i, index = 0, 0 while(index < len(lst)): element_count = 0 while(i < len(lst) and lst[i] == lst[index]): element_count += 1 i += 1 tup_list.append((lst[index], element_count)) index += element_count return tup_list# Driver Codelst = [1, 1, 1, 2, 2, 3, 3, 4]print(shrinkList(lst)) |
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time Complexity: O(n) where n is the number of elements in the input list.
Auxiliary Space: O(n)
Alternate Brute force Approach for Shrink given list for Repeating Elements
This is another brute-force approach that uses for loop to traverse the list. It uses a variable ‘prev_element’ to store the previous element. First, it checks if this is the first unique element or not, if yes, It increments the counter and stores the element to prev_element. If the element is repeated, just increment the counter. If all these cases are not true then just append the prev_element and count as tuple to tup_list.
Python3
# Python3 program to Shrink list # for repeating elementsdef shrinkList(lst): prev_element = None count = 0 tup_list = [] for ele in lst: if (prev_element == ele): count += 1 elif (prev_element is None): count += 1 prev_element = ele else: tup_list.append((prev_element, count)) count = 1 prev_element = ele tup_list.append((prev_element, count)) return tup_listlst = [1, 1, 1, 2, 2, 3, 3, 4]print(shrinkList(lst)) |
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time complexity: O(n), where n is the length of the input list lst. This is because the function iterates through the list once and performs a constant amount of operations for each element in the list.
Auxiliary space: O(n), because the function creates a new list of tuples, where each tuple has two elements (the value and the count of that value in the original list). The size of the new list is proportional to the number of distinct elements in the original list, which is at most n.
Shrink Given List for Repeating Elements using Itertools.group by()
This is a more Pythonic approach to solving the given problem. The itertools. groupby() makes an iterator that returns consecutive keys and groups from the iterable. It groups similar elements and returns the elements and their count as list of tuples.
Python3
# Python3 program to Shrink list # for repeating elementsfrom itertools import groupbydef shrinkList(lst): return ([(element, len(list(i))) for element, i in groupby(lst)])# Driver Codelst = [1, 1, 1, 2, 2, 3, 3, 4]print(shrinkList(lst)) |
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time Complexity: O(n), where n is the number of elements in the list. The time complexity is O(n) because the program iterates through the list once, using the group bycount’s function from the itertools module, which has a time complexity of O(n).
Auxiliary Space: O(n), where n is the number of elements in the list. The auxiliary space is O(n) because the program creates a new list of tuples with the same number of elements as the original list.
Shrink Given List for Repeating Elements using Ordered Dict
Here is an explanation of the code:
- Initialize an OrderedDict to store the counts of each element in the list. Iterate through the list and add each element to the count’scount’s dictionary, incrementing its count if it is already present.
- Initialize an empty list to store the result. Iterate through the count’s dictionary and append each element as a tuple (key, value) to the result list.
- Return the result list.
Python3
from collections import OrderedDictdef shrinkList(lst): # Initialize an OrderedDict to store the counts of each element in the list counts = OrderedDict() # Iterate through the list and add each element to the counts dictionary # If the element is already present, increment its count # If it is not present, add it to the dictionary with a count of 1 for element in lst: if element in counts: counts[element] += 1 else: counts[element] = 1 # Iterate through the counts dictionary and append each element as a tuple # (key, value) to the result list result = [(key, value) for key, value in counts.items()] # Return the result list return result# Test the functionlst = [1, 1, 1, 2, 2, 3, 3, 4]print(shrinkList(lst))#This code is contributed by Edula Vinay Kumar Reddy |
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time complexity: O(n)
Auxiliary space: O(n)
Shrink Given List for Repeating Elements using Set() and Count() Methods
Python’s set() and count() methods in combination used to shrink a given list and remove repeating elements.The set() method is used to create a set, which is an unordered collection of unique elements. By converting the list to a set, duplicate elements are automatically removed. After that, we can use the count() method to determine the number of occurrences of each element in the original list.
Python3
# Python3 program to Shrink list# for repeating elementsdef shrinkList(lst): tup_list = [] x=set(lst) for i in x: tup_list.append((i,lst.count(i))) return tup_list# Driver Codelst = [1, 1, 1, 2, 2, 3, 3, 4]print(shrinkList(lst)) |
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time complexity: O(n)
Auxiliary space: O(n)
Shrink Given List for Repeating Elements using Numpy
We can use the Numpy.unique function to find the unique elements in the array and their respective counts. Then we can create a list of tuples with the element and its count for each unique element.
Python3
import numpy as npdef shrinkList(lst): unique_elements, counts = np.unique(lst, return_counts=True) tup_list = list(zip(unique_elements, counts)) return tup_list# Driver codelst =[1, 1, 1, 2, 2, 3, 3, 4]tup_list = shrinkList(lst)print(tup_list) |
Output
[(1, 3), (2, 2), (3, 2), (4, 1)]
Time complexity: O(nlogn), where n is the number of elements in the input list. The NumPy.unique function has a time complexity of O(nlogn) because it sorts the input array before finding the unique elements. The list creation and zip operation are both O(n).
Auxiliary space: O(n), because the function creates a new list of tuples, where each tuple has two elements (the value and the count of that value in the original list). The size of the new list is proportional to the number of distinct elements in the original list, which is at most n. The NumPy.unique function also creates two arrays of size n, one for the unique elements and one for their counts.
