Index elements of a sequence by where they would appear in a sorted copy

Question

I have a list of integers, for example:

my_list = [5, 2, 4, 9]

I want a list containing the position where each element would appear in the list if it were sorted. So in the example above, I want this result:

>>> sorted(my_list)
[2, 4, 5, 9]

>>> magnitude(my_list)
[2, 0, 1, 3]

... because after sorting:

• 5 ends up in position 2
• 2 ends up in position 0
• 4 ends up in position 1
• 9 ends up in position 3

How can I do that?

Answer 1

We can get half way to the solution by sorting an enumeration of the sequence – for example:

>>> from operator import itemgetter
>>> second_item = itemgetter(1)
>>> my_list = [5, 2, 4, 9]
>>> sorted(enumerate(my_list), key=second_item)
[(1, 2), (2, 4), (0, 5), (3, 9)]

As you can see, each pair in the resulting list has the form (original_position, sorted_item) ... so that for example, 5 was originally in position 0.

We can write a function that just returns those original positions:

def order(s):
    return [t[0] for t in sorted(enumerate(s), key=second_item)]

Let's make sure that it works:

>>> order(my_list)
[1, 2, 0, 3]

The clever bit is that now we run the same function again on its own result:

>>> order([1, 2, 0, 3])
[2, 0, 1, 3]

To understand what's happening here, lets go back and see what order() is actually doing:

>>> sorted(enumerate([1, 2, 0, 3]), key=second_item)
[(2, 0), (0, 1), (1, 2), (3, 3)]

Again, each pair has the form (original_position, sorted_item), so we're effectively sorting the positions back into their original order and seeing where they end up.

All we need to do now is wrap that double use of order() in its own function, and we're done:

from operator import itemgetter

second_item = itemgetter(1)

def order(s):
    return [t[0] for t in sorted(enumerate(s), key=second_item)]

def magnitude(s):
    return order(order(s))

... and here it is in action:

>>> magnitude([5, 2, 4, 9])
[2, 0, 1, 3]

Answer 2

In [8]: L = [5,2,4,9]

In [9]: LL = sorted(L)

In [10]: LL
Out[10]: [2, 4, 5, 9]

In [11]: sorted(enumerate(LL), key=lambda t: L.index(t[1]))
Out[11]: [(2, 5), (0, 2), (1, 4), (3, 9)]

In [12]: [s[0] for s in sorted(enumerate(LL), key=lambda t: L.index(t[1]))]
Out[12]: [2, 0, 1, 3]