Python | Accumulative index summation in tuple list

Sometimes, while working with data, we can have a problem in which we need to find accumulative summation of each index in tuples. This problem can have applications in web development and competitive programming domain. Let’s discuss certain way in which this problem can be solved. 

Method 1: Using accumulate() + sum() + lambda + map() + tuple() + zip() The combination of above functions can be used to solve this task. In this, we pair the elements using zip(), then we perform the sum of them and we extend this to all elements using map(). The taking forward of sum is done by using accumulate. The binding of all logic is done by lambda function. 

The original list : [(3, 4, 5), (4, 5, 7), (1, 4, 10)]
Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(nm), where n is the number of tuples in the list and m is the length of each tuple. This is because the program iterates over each tuple in the list once and performs an operation on each element of the tuple.
Auxiliary space: O(nm), as the program creates a new list of tuples to store the result of the operation performed on each tuple in the original list.

Method #2: Using numpy.cumsum()

Note: Install numpy module using command “pip install numpy”

This method uses the cumsum() function from the numpy library to perform the cumulative sum of the tuple list. This function takes the input array and performs the cumulative sum along the specified axis.

Output :

The original list : [(3, 4, 5), (4, 5, 7), (1, 4, 10)]
Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time Complexity : O(n)
Auxiliary Space : O(n)

Method 3: Using list comprehension

Use a loop to iterate over the tuples in the test_list. For each iteration, extract the first i+1 tuples from the test_list and use the zip function to group the elements with the same index into tuples. then calculate the sum of each of these tuples using a list comprehension and the sum function. Finally, we convert the resulting list of sums into a tuple using the tuple function and append it to the cumulative_sum list.

Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(n^2), where n is the number of tuples in the test_list. 
Auxiliary space: O(n^2), as we store the cumulative sums in a list that has the same length as the test_list. 

Method 4: Using a for loop to iterate over the tuples and calculate the cumulative index summation.

The implementation uses a for loop to iterate over the tuples in the list. If the result list is empty, the current tuple is appended to the result. Otherwise, the previous tuple in the result is retrieved and a new tuple is calculated by adding the corresponding elements of the two tuples. The new tuple is then appended to the result list.

The original list : [(3, 4, 5), (4, 5, 7), (1, 4, 10)]
Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(n*m), where n is the number of tuples in the list and m is the length of each tuple.
Auxiliary space: O(n*m), where n is the number of tuples in the list and m is the length of each tuple.

Method 5: Using itertools.accumulate()

Use the accumulate() function from the itertools module to calculate the cumulative sum of each tuple element-wise. Here’s how you can do it:

• Create a list test_list of tuples, each tuple containing three integers.
• Call the accumulate() function from the itertools module with two arguments: the test_list list and a lambda function that takes two tuples as input and returns a new tuple that is the element-wise       sum of the two input tuples.
• The accumulate() function returns an iterator that generates the cumulative sums of the tuples in the input list. Convert this iterator to a list using the list() function and assign it to the variable res.
• Print the res list, which contains the cumulative sums of the tuples in the input list.

Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(n), where n is the length of the input list test_list. 
Auxiliary space: O(n), because the accumulate() function returns a new list that contains the cumulative sums.

Method 6: Using Recursive method.

Step-by-step approach:

• Initialize an empty list res to store the result.
• Loop through all the tuples in the list.
• If this is the first tuple, append it to the result list.
• Otherwise, get the last tuple in the result list.
• Create a new tuple by adding the corresponding elements of the current tuple and the last tuple.
• Append the new tuple to the result list.
• Return the result list.

Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(n), where n is the number of tuples in the list. This is because the algorithm needs to process each tuple in the list once.
Auxiliary space: O(n), because the space used by the algorithm depends on the size of the input list. The algorithm creates a new list to store the result, which can have at most n tuples. Additionally, the algorithm uses a constant amount of space to store loop variables and temporary tuples.

Method 7: Using reduce() function from functools module

• Import reduce() function from the functools module.
• Define a lambda function that adds the tuples element-wise.
• Use reduce() function to calculate the cumulative sum of the tuples in the list.
• Store the cumulative sum in a new list of tuples.

Accumulative index summation of tuple list : [(3, 4, 5), (7, 9, 12), (8, 13, 22)]

Time complexity: O(n^2), since the reduce() function iterates over the tuples in the list once for each tuple.
Auxiliary space: O(n), since we are creating a new list of tuples to store the cumulative sum.