Get a slice of a sorted list according to a key in Python

user_11127623 0
Viewed 572

Is it possible to slice a sorted list based on some key value (e.g the length of the list items)? If so, how?

For example I get a sorted list like this:

sorted_list = sorted(some_list, key=len)

Now I want to get a slice containing all items with the lowest and equal len (i.e. all items of len: min(sorted_list, key=len) ) which should be the at the head of the sorted list.

slice sorting python
4 Answers

You can group the items first, then take the elements of the first resulting subiterator.

from itertools import groupby


firsts = list(next(groupby(sorted(some_list, key=len), len))[1])

For example,

>>> some_list = [[1, 2, 3], [4, 5, 6], [1], [2], [2, 3]]
>>> list(next(groupby(sorted(some_list, key=len), len))[1])
[[1], [2]]
user_11268410

You can do it like this:

min_len = len(min(some_list, key=len))
sorted_list = sorted((x for x in some_list if len(x) == min_len), key=len)

What this does is it finds the length of the minimum element in the list, and then filters out the elements that are longer than that when the list is passed into the sorted function. It requires an extra pass over the data to find the min length, but sorting takes much longer than that, so that time-cost is practically irrelevant.

user_59469210

This function sorts the list, gets the key (i.e. the shortest length element), then builds an array containing only elements of equal length.

def slice_list(lst, func=len):
    # start by sorting the list
    sorted_lst = sorted(lst, key=func)

    # get the key
    key = func(sorted_lst[0])

    # get the slice
    slice = [v for v in sorted_lst if func(v) <= key]
    return slice

Since there are no test cases, here is one (if I am interpreting this question correctly)

test = ['abcd', 'abcde', 'efgh', '1234', 'abcdef']
print(slice_list(test, len))

Outputs

['abcd', 'efgh', '1234']
user_159746150

This is more for curiosity than practicality (since itertools is really performant)…you can group by a minimum and avoid the sort in a single pass in the same way you can find the minimum of a list without sorting. Here you just keep track of the current minimum and all the values of the same size. If you find a smaller value scrap the old ones and start again:

some_list = ['999', '11', '22', '343', '12', '545', '99', '11', '100', '11']


def minGroup(l, f):
    it = iter(l)
    
    current = [next(it)]
    curr_min = f(current[0])

    for item in it:
        if f(item) < curr_min:
            curr_min, current = f(item), [item]
        elif f(item) == curr_min:
            current.append(item)

    return current
    

minGroup(some_list, len)
# ['11', '22', '12', '99', '11', '11']

minGroup(some_list, int)
# ['11', '11', '11']
user_38746230
Related