Reverse indices of a sorted list

Question

I want to return the 'reverse' indices of a sorted list. What I mean by that is: I have an unsorted list U and I sort it via S=sorted(U). Now, I can get the sort indices such that U(idx)=S - but I want S(Ridx) = U.

Here a little example:

U=[5,2,3,1,4]

S=sorted(U)

idx = [U.index(S[i]) for i in range(len(U))]
>>> idx
[3, 1, 2, 4, 0]

Ridx = [S.index(U[i]) for i in range(len(U))]
>>> Ridx
[4, 1, 2, 0, 3]

>>>[U[idx[i]] for i in range(len(U))] == S
True

>>>[S[Ridx[i]] for i in range(len(U))] == U
True

What I need is an efficient way to get Ridx.

Thanks!

---

Edit:

All right! I did a little speed test for both of the solutions (@Jon Clements and @Whatang) which answered the question.

The script:

import datetime as DT
import random

U=[int(1000*random.random()) for i in xrange(pow(10,8))]

S=sorted(U)

idx = sorted(xrange(len(U)), key=U.__getitem__)

T0 = DT.datetime.now()
ridx = sorted(xrange(len(U)), key=idx.__getitem__)
print [S[ridx[i]] for i in range(len(U))]==U
elapsed = DT.datetime.now()-T0
print str(elapsed)

print '==============='
T0 = DT.datetime.now()
ridx = [ y for (x,y) in sorted(zip(idx, range(len(idx)))) ]
print [S[ridx[i]] for i in range(len(U))]==U
elapsed = DT.datetime.now()-T0
print str(elapsed)

And the results:

True
0:02:45.278000
===============
True
0:06:48.889000

Thank you all for the quick and meaningful help!

Answer 1

The most efficient I can think of (short of possibly looking to numpy) that gets rid of the .index and can be used for both idx and ridx:

U=[5,2,3,1,4]
idx = sorted(xrange(len(U)), key=U.__getitem__)
ridx = sorted(xrange(len(U)), key=idx.__getitem__)
# [3, 1, 2, 4, 0] [4, 1, 2, 0, 3]

Answer 2

Not quite the data structure you asked for, but I think this gets the info you want:

>>> sorted(x[::-1] for x in enumerate(['z', 'a', 'c', 'x', 'm']))
[('a', 1), ('c', 2), ('m', 4), ('x', 3), ('z', 0)]