Python Easiest Way to Sum List Intersection of List of Tuples

Question

Let's say I have the following two lists of tuples

myList = [(1, 7), (3, 3), (5, 9)]
otherList = [(2, 4), (3, 5), (5, 2), (7, 8)]

returns => [(1, 7), (2, 4), (3, 8), (5, 11), (7, 8)]

I would like to design a merge operation that merges these two lists by checking for any intersections on the first element of the tuple, if there are intersections, add the second elements of each tuple in question (merge the two). After the operation I would like to sort based upon the first element.

I am also posting this because I think its a pretty common problem that has an obvious solution, but I feel that there could be very pythonic solutions to this question ;)

Answer 1

Use a dictionary for the result:

result = {}
for k, v in my_list + other_list:
    result[k] = result.get(k, 0) + v

If you want a list of tuples, you can get it via result.items(). The resulting list will be in arbitrary order, but of course you can sort it if desired.

(Note that I renamed your lists to conform with Python's style conventions.)

Answer 2

Use defaultdict:

from collections import defaultdict
results_dict = defaultdict(int)
results_dict.update(my_list)
for a, b in other_list:
    results_dict[a] += b
results = sorted(results_dict.items())

Note: When sorting sequences, sorted sorts by the first item in the sequence. If the first elements are the same, then it compares the second element. You can give sorted a function to sort by, using the key keyword argument:

results = sorted(results_dict.items(), key=lambda x: x[1]) #sort by the 2nd item

or

results = sorted(results_dict.items(), key=lambda x: abs(x[0])) #sort by absolute value

Answer 3

A method using itertools:

>>> myList = [(1, 7), (3, 3), (5, 9)]
>>> otherList = [(2, 4), (3, 5), (5, 2), (7, 8)]

>>> import itertools
>>> merged = []
>>> for k, g in itertools.groupby(sorted(myList + otherList), lambda e: e[0]):
...    merged.append((k, sum(e[1] for e in g)))
... 
>>> merged
[(1, 7), (2, 4), (3, 8), (5, 11), (7, 8)]

This first concatenates the two lists together and sorts it. itertools.groupby returns the elements of the merged list, grouped by the first element of the tuple, so it just sums them up and places it into the merged list.