Remove repeating tuples from a list, depending on the values in the tuples

Question

I have a list of tuples. Each tuple contains 2 elements:

• The 1st element is a tuple with some numbers, e.g. (1, 4, 2). This is in fact a path, the numbers in which are IDs of nodes.
• The 2nd element is a number, which is a score of the path.

For example, the list may be

pathList = [
    ((1, 2),    4),
    ((1, 4, 2), 2),
    ((1, 2),    6),
    ((1, 2),    3),
    ((1, 4, 2), 3)
]

Now I want to remove tuples which have the same paths (1st element) as others, while keeping the one that has the highest score (2nd element) among them.

For example, after the process, pathList should be

pathList = [
    ((1, 2),    6),
    ((1, 4, 2), 3)
]

The order is not important.

Is there an efficient way to do it?

Answer 1

You can use a dictionary (dict.setdefault method)to preserve your paths as key and relative scores as a set (O(1) complexity for adding values) of values then select the max score for each unique path :

>>> pathList = [
...     ((1, 2),    4),
...     ((1, 4, 2), 2),
...     ((1, 2),    6),
...     ((1, 2),    3),
...     ((1, 4, 2), 3)
... ]
>>> 
>>> d={}
>>> for i,j in pathList:
...   d.setdefault(i,set()).add(j)
... 
>>> [(i,max(j)) for i,j in d.items()]
[((1, 2), 6), ((1, 4, 2), 3)]