Sorting and filtering a list

Question

I have list like this:

[['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'],
 ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'],
 ['Gordon', 2, 'Group A']]

That I would like to filter so that only the lowest number (Richard has a number of 1, Mark is 3, Alan is 4, etc.) of each group is kept so that the list would look like:

[['Richard', 1, 'Group A'], ['Dave', 3, 'Group B']]

I'm sorting with the lambda key:

filteredList = sorted(list,key=lambda x: x[2])

But I'm blocked when it comes to sorting within each group and getting rid of higher ranking individuals.

Is there a simple way to achieve this in Python or should I iterate and test each row?

Answer 1

Re-key the data off of the group name. Don't name your data list because it shadows a built-in name.

>>> results = {}
>>> for name, number, group in data:
...     key = group
...     value = number, name
...     results[key] = min(value, results.get(key, value))
...     
>>> [[name, number, group] for group, (number, name) in results.items()]
[['Dave', 3, 'Group B'], ['Richard', 1, 'Group A']]

Pure python data structures handle this problem quite nicely, the sort/itertools approach is suboptimal and increases complexity from O(n) to O(n logn).

Answer 2

You can use collections.defaultdict in order to group your sub lists based on 3rd item then use min() function with a proper key within a list comprehension in order to get the expected result:

In [61]: from operator import itemgetter
In [62]: from collections import defaultdict
In [63]: lst = [['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'], ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'], ['Gordon', 2, 'Group A']]

In [64]: d = defaultdict(list)

In [65]: for i, j, k in lst:
             d[k].append([i, j, k])
   ....:     

In [66]: [min(sub, key=itemgetter(1)) for sub in d.values()]
Out[66]: [['Dave', 3, 'Group B'], ['Richard', 1, 'Group A']]

You can do this even in a more optimized manner by passing a customized object to defaultdict(), so that it only appends new items if they have a smaller second item:

from collections import defaultdict


class MyList(list):

    def __init__(self, *args, **kwargs):
        super(MyList, self).__init__(*args, **kwargs)

    def special_append(self, arg):
        if not self:
            self.append(arg)
        elif arg[1] < self[0][1]:
            self[0] = arg

Demo:

lst = [['Richard', 1, 'Group A'], ['Mark', 3, 'Group A'], ['Alan', 4, 'Group B'], ['Dave', 3, 'Group B'], ['Gordon', 2, 'Group A']]

d = defaultdict(MyList)

for i, j, k in lst:
    d[k].special_append([i, j, k])

print(d)

defaultdict(<class '__main__.MyList'>, {'Group B': [['Dave', 3, 'Group B']], 'Group A': [['Richard', 1, 'Group A']]})