Python – Elements Frequency in Mixed Nested Tuple

Sometimes, while working with Python data, we can have a problem in which we have data in the form of nested and non-nested forms inside a single tuple, and we wish to count the element frequency in them. This kind of problem can come in domains such as web development and Data Science. Let’s discuss certain ways in which this task can be performed.

Input : test_tuple = (5, (6, (7, 8, 6))) 
Output : {5: 1, 6: 2, 7: 1, 8: 1} 

Input : test_tuple = (5, 6, 7, 8)
 Output : {5: 1, 6: 1, 7: 1, 8: 1}

Method #1: Using recursion + loop

The solution to this problem involved two steps. At first, we perform flattening of tuples using recursion and then the counting is performed in a brute force manner using loop. 

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Method #2: Using Counter() + recursion

This is yet another way in which this problem can be solved. In this, we employ Counter() to perform the task of counting elements. 

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Method #3 : Using type(),extend(),list(),set() and count() functions

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Method #4 : Using type(),extend(),list(),set() and operator.countOf() methods

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Time Complexity: O(N*N)
Auxiliary Space: O(N)

Method #5: Using recursion and defaultdict

This code defines a function count_elements(t) that takes a tuple t as input and returns a dictionary with the frequency of each element in the tuple. The function uses a defaultdict from the collections module to create the dictionary with a default value of zero for any new key.

The function iterates over each element in the input tuple t. If the element is an integer, it increments the count of that integer in the dictionary. If the element is a tuple, it recursively calls the count_elements function on that tuple and adds the resulting frequencies to the main dictionary.

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : defaultdict(<class 'int'>, {5: 2, 6: 2, 7: 1, 8: 1, 9: 2})

Time complexity: O(n)
The for loop iterates over each element in the input tuple once. In the worst case, the tuple can contain nested tuples, so the loop may need to iterate over the entire nested structure. The defaultdict and dict operations are O(1) time complexity. The is instance check and the recursive call to count_elements are O(1) time complexity in the average case, but in the worst case when the tuple is deeply nested, the time complexity could approach O(n), where n is the total number of elements in the tuple. Therefore, the overall time complexity of this function is O(n), where n is the total number of elements in the tuple.

Auxiliary Space:O(n)
The freq dictionary stores the frequencies of each element in the tuple. In the worst case, if all elements in the tuple are unique, the dictionary will have n entries, where n is the number of elements in the tuple.
The recursive calls to count_elements create new dictionaries for each nested tuple in the worst case. Therefore, the overall space complexity of this function is O(n), where n is the total number of elements in the tuple.

Method#6: Using nested loop

Algorithm: Counting the frequency of elements

1. Initialize an empty dictionary freq to store the frequency of elements.
2. Loop through each item in the input tuple t.
3. If the item is an integer, check if it already exists in the dictionary. If not, add it to the dictionary with a value of 0.
4. Increment the value of the item in the dictionary by 1.
5. If the item is a tuple, loop through each subitem in the tuple. If the subitem is an integer, check if it already exists in the dictionary. If not, add it to the dictionary with a value of 0. Increment the value of the subitem in the dictionary by 1.
6. Return the dictionary freq with the frequency of elements.

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Time complexity: O(N * M), where n is the number of items in the input tuple t, and m is the maximum number of integers in any tuple within t. This is because we need to loop through each item in t and each subitem in any tuple in t that contains integers. 

Auxiliary space: O(K), where k is the number of unique integers in t, because we store each unique integer as a key in the freq dictionary. However, this could be higher if there are many tuples with many unique integers.

Method #7: Using replace(),list(),map(),set(),split(),count() functions

Note: Here we will be converting the tuple to string

The original tuple : (5, 6, (5, 6), 7, (8, 9), 9)
The elements frequency : {5: 2, 6: 2, 7: 1, 8: 1, 9: 2}

Time Complexity : O(N) N – length of z
Auxiliary Space : O(N) N – length of res