9

Suppose I have a list of tuples:

x = [(1,2), (3,4), (7,4), (5,4)]

Of all tuples that share the second element, I want to preserve the tuple with the largest first element:

y = [(1,2), (7,4)]

What is the best way to achieve this in Python?


Thanks for the answers.

  • The tuples could be two-element lists instead, if that makes a difference.
  • All elements are nonnegative integers.
  • I like the current answers. I should really learn more about what collections has to offer!
7
  • Do you need to retain the order of the tuples; that is, if the original is [(a, b), (x, y)], then the output must have [(a, b), (x, y)] as the order, or is [(x, y), (a, b)] acceptable? Do you need to retain the order of the integers within the tuples; that is, is [(b, a), (y, x)] acceptable?
    – gotgenes
    Nov 6, 2010 at 0:44
  • The order within tuples must be preserved. The order among tuples in the list should be preserved, but they can easily be sorted using y.sort() which will operate on the first element of each tuple.
    – Steve Tjoa
    Nov 6, 2010 at 0:51
  • 1
    @Steve I believe your assertion that the order of appearance of tuples in the list be preserved contradicts declaring they may also be sorted using sort(), unless there is an unstated assumption in your question that the input list is sorted by the first element of the tuples.
    – gotgenes
    Nov 6, 2010 at 1:12
  • What I meant was, if y were not sorted, it could easily become sorted.
    – Steve Tjoa
    Nov 6, 2010 at 1:17
  • 1
    @Steve, my answer and pillmunchers answer both get taken out without modification if the items to compare will be a list. Any list will compare as less than any tuple. The solution would be to cast to a tuple or list uniformly but that would get awkward. Gnibbler's answer is probably best for you. Nov 6, 2010 at 2:05

5 Answers 5

5

Similar to Aaron's answer

>>> from collections import defaultdict
>>> x = [(1,2), (3,4), (7,4), (5,4)]
>>> d = defaultdict(int)
>>> for v,k in x:
...   d[k] = max(d[k],v) 
... 
>>> y=[(k,v) for v,k in d.items()]
>>> y
[(1, 2), (7, 4)]

note that the order is not preserved with this method. To preserve the order use this instead

>>> y = [(k,v) for k,v in x if d[v]==k]
>>> y
[(1, 2), (7, 4)]

here is another way. It uses more storage, but has less calls to max, so it may be faster

>>> d = defaultdict(list)
>>> for k,v in x:
...   d[v].append(k)
... 
>>> y = [(max(k),v) for v,k in d.items()]
>>> y
[(1, 2), (7, 4)]

Again, a simple modification preserves the order

>>> y = [(k,v) for k,v in x if max(d[v])==k]
>>> y
[(1, 2), (7, 4)]
0
5

use collections.defaultdict

import collections

max_elements = collections.defaultdict(tuple)

for item in x:
    if item > max_elements[item[1]]:
        max_elements[item[1]] = item

y = max_elements.values()
6
  • Thank you for the answer. I was already tinkering with your earlier answer which did work for my particular case. May I ask why you changed it?
    – Steve Tjoa
    Nov 6, 2010 at 0:40
  • @Steve, this only iterates once and will use much less memory for a larger list. All in all, it's much better. Nov 6, 2010 at 0:46
  • 1
    Thanks. I would upvote, but SO is locking me out because I upvoted, then canceled (before I could fully understand the answer), then thought I could re-upvote.
    – Steve Tjoa
    Nov 6, 2010 at 0:54
  • As it currently stands, this gives me the following error: TypeError: 'int' object is not subscriptable for the line if item[0] > max_elements[item[1]][0]: when attempting to use it with the value of x shown in the question.
    – martineau
    Nov 6, 2010 at 1:28
  • @aaronasterling: Your fix got rid of the TypeError I pointed out, but your solution doesn't preserve tuple order. e.g. It's gives the same result for both x = [(1,2), (3,4), (7,4), (5,4)] and x = [(3,4), (7,4), (5,4), (1,2)], namely [(1, 2), (7, 4)].
    – martineau
    Nov 6, 2010 at 2:36
2

If you can make the assumption that tuples with identical second elements appear in contiguous order in the original list x, you can leverage itertools.groupby:

import itertools
import operator

def max_first_elem(x):
    groups = itertools.groupby(x, operator.itemgetter(1))
    y = [max(g[1]) for g in groups]
    return y

Note that this will guarantee preservation of the order of the groups (by the second tuple element), if that is a desired constraint for the output.

0

My own attempt, slightly inspired by aaronsterling:

(oh yeah, all elements are nonnegative)

def processtuples(x):
    d = {}
    for item in x:
        if x[0] > d.get(x[1],-1):
            d[x[1]] = x[0]

    y = []
    for k in d:
        y.append((d[k],k))
    y.sort()
    return y
0
>>> from collections import defaultdict
>>> d = defaultdict(tuple)
>>> x = [(1,2), (3,4), (7,4), (5,4)]
>>> for a, b in x:
...     d[b] = max(d[b], (a, b))
...
>>> d.values()
[(1, 2), (7, 4)

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.