Given a list of tuples, the task is to sum the tuples having the same first value.
Examples:
Input: [(1, 13), (2, 190), (3, 82), (1, 12)] Output: [(1, 25), (2, 190), (3, 82)]
Input: [(1, 13), (1, 190), (3, 25), (1, 12)] Output: [(1, 215), (3, 25)]
Let us discuss the different ways we can do this task.
Method #1: Using map()
Python3
# Python code to get sum of tuples having same first value# Initialisation of list of tupleInput = [(1, 13), (1, 190), (3, 25), (1, 12)]d = {x: 0 for x, _ in Input}for name, num in Input: d[name] += num# using mapOutput = list(map(tuple, d.items()))# printing outputprint(Output) |
[(1, 215), (3, 25)]
Time Complexity: O(n)
Auxiliary Space: O(n)
Method #2: Using defaultdict
Python3
# Python code to sum list of tuples having same first value# Importingfrom collections import defaultdict# Initialisation of list of tupleInput = [(2, 190), (1, 13), (1, 12), (2, 14), (3, 82), (1, 70)]# Initialisation of defaultdictoutput = defaultdict(int)for k, v in Input: output[k] += v# Printing outputprint(list(output.items())) |
[(1, 95), (2, 204), (3, 82)]
Time complexity: O(n), where n is the number of tuples in the Input list.
Auxiliary space: O(k), where k is the number of unique keys in the Input list.
Method #3: Using for loop
Python3
# Python code to get sum of tuples having same first value# Initialisation of list of tupleInput = [(1, 13), (1, 190), (3, 25), (1, 12)]Output = []x=[]for i in Input: if i[0] not in x: x.append(i[0])for i in x: p=[] p.append(i) s=0 for j in Input: if(j[0]==i): s+=j[1] p.append(s) Output.append(tuple(p))# printing outputprint(Output) |
[(1, 215), (3, 25)]
Time complexity: O(n^2) – nested loop over the input list
Auxiliary space: O(n) – creating a new list to store unique first values of tuples.
Method #4: Using a dictionary comprehension
Approach is using a dictionary comprehension to sum the tuples with the same first value. Here is an example of how this could be done:
Python3
def sum_tuples(input_list): # Create a dictionary with the first values of the tuples as keys # and the sum of the second values as values sums = {key: sum(t[1] for t in input_list if t[0] == key) for key, _ in input_list} # Return the dictionary as a list of tuples return [(key, value) for key, value in sums.items()]input_list = [(1, 13), (1, 190), (3, 25), (1, 12)]print(sum_tuples(input_list)) # [(1, 215), (3, 25)]#This code is contributed by Edula Vinay Kumar Reddy |
[(1, 215), (3, 25)]
This approach first creates a dictionary with the first values of the tuples as keys and the sum of the second values as values. It then converts the dictionary back into a list of tuples using a dictionary comprehension. This method is relatively concise and easy to understand, and should be efficient for most cases. However, it may not be as efficient as some of the other methods mentioned in the article if you are working with extremely large lists of tuples.
Method #5:Using itertools groupby
- groupby() groups the input list by the first element of each tuple.
- The lambda function lambda x: x[0] is used as the key function to group by the first element of each tuple.
- sum(v for _, v in group) is used to compute the sum of values in each group.
- (k, sum(v for _, v in group)) is used to create new tuples with the first element being the key and the second element being the sum of values in each group.
- Input.sort(key=lambda x: x[0]) sorts the input list by the first element of each tuple, which is required by groupby().
Python3
from itertools import groupby# Initialisation of list of tupleInput = [(1, 13), (1, 190), (3, 25), (1, 12)]# sorting the list by the first element of each tupleInput.sort(key=lambda x: x[0])# using groupby from itertools to group tuples by the first elementgroups = groupby(Input, lambda x: x[0])# computing the sum of values in each group and creating new tuplesoutput = [(k, sum(v for _, v in group)) for k, group in groups]print(output)#This code is contributed by Vinay Pinjala. |
[(1, 215), (3, 25)]
The time complexity of this solution is O(n log n), where n is the number of tuples in the input list. This is because the first step of the algorithm sorts the list based on the first element of each tuple, which has a time complexity of O(n log n) in the average case.
The auxiliary space of this solution is O(n), where n is the number of tuples in the input list. This is because the algorithm needs to store a sorted version of the input list and a dictionary to keep track of the sum of values for each unique first value in the input list. The size of these data structures will be proportional to the size of the input list, which is O(n).
Method 6: Using the pandas library.
Step-by-step approach:
- Import the pandas library.
- Create a pandas dataframe from the input list of tuples.
- Use the groupby() method to group the dataframe by the first column.
- Use the sum() method to get the sum of each group.
- Convert the resulting dataframe back to a list of tuples.
Below is the implementation of the above approach:
Python3
import pandas as pdInput = [(1, 13), (1, 190), (3, 25), (1, 12)]# create dataframe from input listdf = pd.DataFrame(Input)# group by the first column and get the sum of each groupgrouped = df.groupby(0).sum()# convert dataframe back to list of tuplesoutput = [tuple(x) for x in grouped.to_records()]# print outputprint(output) |
Output:
[(1, 215), (3, 25)]
Time complexity: O(n log n), where n is the number of tuples in the input list, due to the use of groupby() which requires sorting the dataframe.
Auxiliary space: O(n) due to the creation of the dataframe.
