Sort list of lists in lexicographic order in Python

Question

I want to get the minimal element of a list of list of tuples

a = [[(1, 0), (2, 0), (1, 1)], [(2, 0), (1, 1), (1, 0)], [(1, 1), (1, 0), (2, 0)]]

in lexicographic order, so that [(1,1),(1,0),(2,0)]] < [(1,0),(2,0),(1,1)] , since the 0-th entry of the tuple has the greater priority, that is 1,1,2 < 1,2,1, and the 1-st entry has less priority.

min(a)

returns [(1, 0), (2, 0), (1, 1)], which of course is not correct.

I only need the index of the minimal element, so an incorrect version would be

print(min(range(len(a)), key=lambda i: a[i]))

(both minimal element and index only methods would be appreciated).

Of course one could write a custom loop with zip or something, but I would like a solution with little overhead.

Answer 1

You can use a custom key, zipping the tuples (zip):

min(a, key=lambda x: list(zip(*x)))

Output: [(1, 1), (1, 0), (2, 0)]

how it works

The default comparison of lists of tuples works by comparing the first tuples, then the second, etc. (sort of depth first while you want breadth first).

Since you want priority on the first item of each tuple, you need to reorganize the tuples. Internally, with this lambda x: list(zip(*x)) key, min sees the items this way:

[list(zip(*x)) for x in a]
# [[(1, 2, 1), (0, 0, 1)], [(2, 1, 1), (0, 1, 0)], [(1, 1, 2), (1, 0, 0)]]

And their sorted order is:

[[(1, 1, 2), (1, 0, 0)], [(1, 2, 1), (0, 0, 1)], [(2, 1, 1), (0, 1, 0)]]

Answer 2

You could use a sort key that picks up only the first element of each tuple:

sorted(a,key=lambda L:[k for k,_ in L]) # effective ordering

[[(1, 1), (1, 0), (2, 0)], [(1, 0), (2, 0), (1, 1)], [(2, 0), (1, 1), (1, 0)]]

min(a,key=lambda L:[k for k,_ in L]) # lowest/first value in that order

[(1, 1), (1, 0), (2, 0)]