53

I have a list where each element is of the form [list of integers, integer]. For example, an element of the list may look like this [[1,3,1,2], -1].

I want to sort a list containing the described type of elements by the following criteria:

  1. if the integer lists of two elements (i.e. element[0]) are of different length, the element with the smaller integer list is the smaller one.

  2. else if the integer lists are of the same length, the smaller element is that which has the smaller integer for the first integer which differs in the integer list of both elements. For example:

    [[1,1,99,100], -1] < [[1,1,100,1], -1], because 99 < 100.

  3. else if the integer lists are identical, the smaller element is the one with the smaller integer in element[1].

How would I write an approriate key function I could pass to sorted() or sort()?

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
timgeb
  • 76,762
  • 20
  • 123
  • 145

2 Answers2

101

List the three criteria in your key:

sorted(inputlist, key=lambda e: (len(e[0]), e[0], e[1]))

Now you are sorting each element first by the length, then by comparing the first element directly (which in only used when the first element is of equal length), then by the value of the last integer.

Python sorts tuples and lists like these lexicographically; compare the first element, and only if that doesn't differ, compare the second element, etc.

The second element here is e[0] which will only be used if both compared entries have nested lists of equal length. These are again compared lexicographically, so pairing up elements until a pair differs.

Martijn Pieters
  • 1,048,767
  • 296
  • 4,058
  • 3,343
  • 2
    What if we want one of the criteria to be a descending order for strings? – Thanasis Nov 19 '19 at 12:52
  • 3
    @Thanasis if all the other criteria are numeric, then negate their values for the sort key and add `reverse=True`. Otherwise, use consecutive sorts, using the rightmost criteria first, then the next, etc. Python’s sort is stable allowing you to combine criteria that way – Martijn Pieters Nov 19 '19 at 13:11
  • 1
    @Thanasis: here’s an answer with code: https://stackoverflow.com/a/55866810/100297 – Martijn Pieters Nov 19 '19 at 13:26
  • I have the following list a = ['01-19 WK', '02-19 WK', '03-19 WK', '01-19 WE', '01-20 WK', '02-20 WK'] and I would like to have the following: a = ['01-19 WK', '01-19 WE', '02-19 WK', '03-19 WK', '01-20 WK', '02-20 WK'] . I have written the following : k = sorted(sorted(a, key =lambda e: (e[3:5], e[:3])), key = lambda e: e[-2:], reverse=True) but it doesn't seem to work – Thanasis Nov 19 '19 at 13:42
  • I think I made it. I just had to reverse the order of the shorting: sorted(sorted(a, key = lambda e: e[-2:], reverse=True), key =lambda e: (e[3:5], e[:3])) – Thanasis Nov 19 '19 at 13:45
21
key = lambda x: (len(x[0]), x[0], x[1])

This works because tuples (and lists) are compared by looking at each element in turn until a difference is found. So when you want to sort on multiple criteria in order of preference, just stick each criterion into an element of a tuple, in the same order.

I'm assuming that by "smaller" you mean the same thing as "lesser", that is to say you don't mean to compare absolute values.

Steve Jessop
  • 273,490
  • 39
  • 460
  • 699