2

For example if I have a list of distinct items:

L = [100,55,104,400]

The "relative" orderings can be restated:

R = [1,0,2,3]

I am not sure how to convert L to R. At first I just tried subtracting min(L) from everything but that doesn't "compress" things down to relative order.

I am looking for an efficient solution (not O(n2)).

Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
user4967499
  • 325
  • 2
  • 5
  • You can also check the other dupe http://stackoverflow.com/questions/3382352/equivalent-of-numpy-argsort-in-basic-python – Bhargav Rao Jun 04 '15 at 22:37
  • This is pretty simple if you know your basic built-in functions: `[i for i, x in sorted(enumerate(L), key=itemgetter(1))]` You can get `itemgetter` from the `operator` module. – Shashank Jun 04 '15 at 22:37
  • This is a bad example. A better example would be `[100,104,55,400]`; should that give `[1,2,0,3]` or `[2,0,1,3]`? –  Jun 05 '15 at 17:46

3 Answers3

2

Use the sorted function and a list comprehension. 

>>> l =  [100,55,104,400]
>>> sortedl = sorted(l)
>>> [sortedl.index(i) for i in l]
[1, 0, 2, 3]

Note that this is O(n2) Answered before edit to ques

Bhargav Rao
  • 50,140
  • 28
  • 121
  • 140
2

You can try a combination of list comprehension, zip, and sorted:

>>> [i[1] for i in sorted(zip(L, range(4)))]
[1, 0, 2, 3]

This is O(nlogn) since you only need to sort once.

zw324
  • 26,764
  • 16
  • 85
  • 118
1

Simple list comprehension:

>>> L = [100, 55, 104, 400]
>>> R = [L.index(i) for i in sorted(L)]
[1, 0, 2, 3]