Given a list, the task is to generate another list containing numbers from 0 to n, from a given list whose each element is the frequency of numbers in the generated list.
Input: freq = [1, 4, 3, 5] Output: [0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3] Explanation: Number = 0 Input[0] = 1 Output = [0] Number =1 Input[1] = 4 Output = [0, 1, 1, 1, 1] (repeats 1 four times) Number =2 Input[2] = 3 Output = [0, 1, 1, 1, 1, 2, 2, 2] (repeats 2 three times) Number =3 Input[3] = 5 Output = [0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3] (repeats 3 five times)
Below are some ways to achieve the above task.
Method #1: Using Iteration
Python3
# Python code to generate list containing numbers from 0 to 'n'# having frequency of no from another list# List initialisationInput = [1, 4, 3, 5]Output = []# Number initialisationno = 0# using iterationfor rep in Input: for elem in range(rep): Output.append(no) no += 1# printing outputprint(Output) |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
Method #2 : Using enumerate and list comprehension
Python3
# Python code to generate list containing numbers from 0 to 'n'# having frequency of no from another list# List initialisationInput = [1, 4, 3, 5]# Using enumerate and list comprehensionOutput = [no for no, rep in enumerate(Input) for elem in range(rep)]# Printing outputprint(Output) |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
Time Complexity: O(n) where n is the number of elements in the list
Auxiliary Space: O(1), extra space is not required
Method #3 : Using enumerate and chain
Python3
# Python code to generate list containing numbers from 0 to 'n'# having frequency of no from another list# List initialisationInput = [1, 4, 3, 5]# Importingfrom itertools import repeat, chain# Using chain and enumerateOutput = list(chain.from_iterable((repeat(x, y)) for x, y in enumerate(Input)))# Printing outputprint(Output) |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
Method #4 : Using extend() method and * operator
Python3
# Python code to generate list containing numbers from 0 to 'n'# having frequency of no from another list# List initialisationInput = [1, 4, 3, 5]Output = []# Number initialisationno = 0# using iterationfor i in Input: Output.extend([no]*i) no += 1# printing outputprint(Output) |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
Method #5: Using repeat()
Using the itertools.repeat function: You can use the repeat function from the itertools module to repeat each element of the frequency list a certain number of times. You can use a for loop to iterate through the frequency list and repeat each element using the repeat function. Here is an example of how you can use the repeat function to generate a list using a given frequency list:
Python3
#Repeat approach to generate a list using a given frequency list#Import the repeat function from the itertools modulefrom itertools import repeat#Initialize the frequency listfrequency_list = [1, 4, 3, 5]#Initialize an empty result listresult = []#Iterate through the frequency listfor i, freq in enumerate(frequency_list): #Repeat each element of the frequency list a certain number of times #and append the repeated elements to the result list result.extend(list(repeat(i, freq)))#Print the result listprint(result)#This code is contributed by Edula Vinay Kumar Reddy |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
The time and space complexity of the repeat approach depend on elements in list. If larger elements present in list then complexity grows.
Method #6: Using zip and list comprehension:
Python3
# List initializationfreq = [1, 4, 3, 5]# Zip the frequency list with the range of the length of the frequency listresult = [i for i, f in zip(range(len(freq)), freq) for _ in range(f)]print(result)# Output: [0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]#This code is contributed by Edula Vinay Kumar Reddy |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
The code first zips the freq list with the range of the length of the freq list. Then, it uses a list comprehension to iterate through the zipped list and create a new list.
The outer list comprehension [i for i, f in zip(range(len(freq)), freq)] iterates through the zipped list, where i is the index and f is the frequency.
The inner list comprehension [i for _ in range(f)] creates a list of f copies of i. This inner list comprehension is nested inside the outer list comprehension, so it is executed for every element in the zipped list.
Finally, the resulting lists are flattened into a single list, which is stored in the result variable.
The time and space complexity of the repeat approach depend on elements in list. If larger elements present in list then complexity grows.
Approach: Using the accumulate function from the itertools module
In this approach, we use the accumulate function from the itertools module to calculate the cumulative sum of the frequency list. The cumulative sum of the frequency list at index i gives us the total number of times the numbers 0 to i-1 will appear in the final list. We can then use this information to generate the final list.
Algorithm:
- Initialize an empty list called result to store the final output.
- Initialize a variable called total to 0.
- Use the accumulate function from the itertools module to calculate the cumulative sum of the frequency list.
- For each element i in the cumulative sum of the frequency list: Append i – total copies of the number corresponding to the current index to the result list.
- Update the total variable to i.
- Return the result list.
Python3
# Import the accumulate function from the itertools modulefrom itertools import accumulate# Function to generate a list using a given frequency listdef generate_list_using_accumulate(frequency_list): # Initialize an empty list called result to store the final output result = [] # Initialize a variable called total to 0 total = 0 # Use the accumulate function to calculate the cumulative sum of the frequency list cumulative_sum = list(accumulate(frequency_list)) # Iterate through the cumulative sum of the frequency list for i in cumulative_sum: # Append i - total copies of the number corresponding to the current index to the result list result.extend([cumulative_sum.index(i)] * (i - total)) # Update the total variable to i total = i # Return the result list return result# Test the function with the given examplefrequency_list = [1, 4, 3, 5]print(generate_list_using_accumulate(frequency_list)) # Output: [0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3] |
[0, 1, 1, 1, 1, 2, 2, 2, 3, 3, 3, 3, 3]
Time Complexity: O(n), where n is the number of elements in the frequency list.
Space Complexity: O(n), where n is the number of elements in the frequency list.
