Given a List, get fractional frequency of each element at each position.
Input : test_list = [4, 5, 4, 6, 7, 5, 4, 5, 4]
Output : [‘1/4’, ‘1/3’, ‘2/4’, ‘1/1’, ‘1/1’, ‘2/3’, ‘3/4’, ‘3/3’, ‘4/4’]
Explanation : 4 occurs 1/4th of total occurrences till 1st index, and so on.
Input : test_list = [4, 5, 4, 6, 7, 5]
Output : [‘1/2’, ‘1/2’, ‘2/2’, ‘1/1’, ‘1/1’, ‘2/2’]
Explanation : 4 occurs 1/2th of total occurrences till 1st index, and so on.
Method : Using Counter() + loop + dictionary comprehension
In this, we use Counter() to get the frequency of each element in list and to form denominator part of fraction. Numerator is initialized to 0 for each element. Then loop is used to add the elements in numerator and join with total frequency in denominator.
Python3
# Python3 code to demonstrate working of # Fractional Frequency of elements in List# Using Counter() + loop + dictionary comprehensionfrom collections import Counter# initializing listtest_list = [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6]# printing original listprint("The original list is : " + str(test_list))# initializing numeratornumber = {idx : 0 for idx in set(test_list)}# initializing denominatordenom = Counter(test_list)res = []for ele in test_list: # increasing counter number[ele] += 1 res.append(str(number[ele]) + '/' + str(denom[ele]))# printing result print("Fractional Frequency List : " + str(res)) |
The original list is : [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6] Fractional Frequency List : ['1/5', '1/3', '2/5', '1/3', '1/1', '2/3', '3/5', '3/3', '4/5', '2/3', '5/5', '3/3']
Time Complexity: O(n*n), where n is the length of the input list.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list “test_list”.
Method : Using list(),set(),count() methods
Approach
- Create a dictionary with unique values of list as keys and values as their occurences in original list (using list(),set(),count()) methods
- Initiate a for loop to traverse the original list to append the fractional frequency of output list(using count())
- Display output list
Python3
# Python3 code to demonstrate working of# Fractional Frequency of elements in List# initializing listtest_list = [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6]# printing original listprint("The original list is : " + str(test_list))x=list(set(test_list))d=dict()for i in x: d[i]=test_list.count(i)res=[]for i in range(0,len(test_list)): a=test_list[:i+1].count(test_list[i]) res.append(str(a)+"/"+str(d[test_list[i]]))# printing resultprint("Fractional Frequency List : " + str(res)) |
The original list is : [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6] Fractional Frequency List : ['1/5', '1/3', '2/5', '1/3', '1/1', '2/3', '3/5', '3/3', '4/5', '2/3', '5/5', '3/3']
Time Complexity: O(n*n), where n is the length of the input list.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list “test_list”.
Method : Using numpy:
Algorithm:
- Initialize an empty list “freq_list”.
- Find the unique values and their respective counts in the given list “test_list” using numpy’s unique() method.
- For each unique value, get the indices where the value occurs in “test_list” using numpy’s where() method.
- For each index of the unique value, calculate the fractional frequency by dividing the count of the value by the number of times it occurs in the sublist from the start of “test_list” up to the current index.
- Append the fractional frequency to the “freq_list”.
- Print the “freq_list”.
Python3
import numpy as nptest_list = [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6]print("The original list is : " + str(test_list))unique_vals, counts = np.unique(test_list, return_counts=True)freq_list = []for val, count in zip(unique_vals, counts): indices = np.where(test_list == val)[0] for i in range(len(indices)): freq_list.append( "{}/{}".format(np.count_nonzero(test_list[:indices[i]+1] == val), count)) print("Fractional Frequency List : " + str(freq_list))# This code is contributed by Jyothi Pinjala |
Output:
The original list is : [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6] Fractional Frequency List : ['1/5', '2/5', '3/5', '4/5', '5/5', '1/3', '2/3', '3/3', '1/3', '2/3', '3/3', '1/1']
Time Complexity: O(n^2), where n is the length of the input list. The worst-case scenario occurs when all the elements of the list are unique and the nested loop runs n times for each element.
Space Complexity: O(n), where n is the length of the input list. The space required by the “freq_list” increases linearly with the length of the input list.
Method : Using list(), set(), operator.countOf() methods:
Approach:
- Create a dictionary with unique values of the list as keys and values as their occurrences in the original list (using list(),set(),operator.countOf()) methods.
- Initiate a for loop to traverse the original list to append the fractional frequency of output list(using operator.countOf()).
- Display the output list.
Below is the implementation of the above approach:
Python3
# Python3 code to demonstrate working of# Fractional Frequency of elements in Listimport operator# initializing listtest_list = [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6]# printing original listprint("The original list is : " + str(test_list))x = list(set(test_list))d = dict()for i in x: d[i] = operator.countOf(test_list, i) res = []for i in range(0, len(test_list)): a = operator.countOf(test_list[:i+1], test_list[i]) res.append(str(a)+"/"+str(d[test_list[i]])) # Print the resultprint("Fractional Frequency List : " + str(res)) |
The original list is : [4, 5, 4, 6, 7, 5, 4, 5, 4, 6, 4, 6] Fractional Frequency List : ['1/5', '1/3', '2/5', '1/3', '1/1', '2/3', '3/5', '3/3', '4/5', '2/3', '5/5', '3/3']
Time Complexity: O(n*n), where n is the length of the input list.
Auxiliary Space: O(n) additional space of size n is created where n is the number of elements in the list “test_list”.
