Given the "confused" list L, get a list in which each element is the index of the corresponding element L, if L was sorted

Question

Desired output

I want the function to return the list in such a way that, given the "confused" list l , each element is the index of the corresponding element l if l was sorted. (I'm not thinking of a less confusing way of saying this, sorry.)

<strong> Examples

f([3,1,2]) = [2,0,1]

f([3,1,2,2,3]) = [3,0,1,2,4] , since the input is sorted [1,2,2,3,3] .

(This is useful for some statistical calculations.)

My attempt

I came up with a way to execute this function, but it's python - it looks like there should be a one-line or at least a much cleaner and cleaner way for this.

 def getIndiciesInSorted(l): sortedL = sorted(l) outputList = [] for num in l: sortedIndex = sortedL.index(num) outputList.append(sortedIndex) sortedL[sortedIndex] = None return outputList l=[3,1,2,2,3] print getIndiciesInSorted(l) 

So how can I write this more briefly? Is there a clear understanding of understanding the text?

Answer 1

 def argsort(seq): # http://stackoverflow.com/questions/3382352/3382369#3382369 # http://stackoverflow.com/questions/3071415/3071441#3071441 ''' >>> seq=[1,3,0,4,2] >>> index=argsort(seq) [2, 0, 4, 1, 3] Given seq and the index, you can construct the sorted seq: >>> sorted_seq=[seq[x] for x in index] >>> assert sorted_seq == sorted(seq) Given the sorted seq and the index, you can reconstruct seq: >>> assert [sorted_seq[x] for x in argsort(index)] == seq ''' return sorted(range(len(seq)), key=seq.__getitem__) def f(seq): idx = argsort(seq) return argsort(idx) print(f([3,1,2])) # [2, 0, 1] print(f([3,1,2,2,3])) # [3, 0, 1, 2, 4] 

---

Please note that the night shift function is faster:

 def get_sorted_indices(l): sorted_positions = sorted(range(len(l)), key=l.__getitem__) result = [None for _ in range(len(l))] for new_index, old_index in enumerate(sorted_positions): result[old_index] = new_index return result 

The difference can be significant for long lists:

 In [83]: import random In [98]: l = [random.randrange(100) for _ in range(10000)] In [104]: timeit get_sorted_indices(l) 100 loops, best of 3: 4.73 ms per loop In [105]: timeit f(l) 100 loops, best of 3: 6.64 ms per loop 

Answer 2

This is the best I came up with:

 def get_sorted_indices(l): sorted_positions = sorted(range(len(l)), key=l.__getitem__) result = [None for _ in range(len(l))] for new_index, old_index in enumerate(sorted_positions): result[old_index] = new_index return result 

This is faster than your decision, but more about that.

Answer 3

There's a one line understanding, but it's really ugly:

 >>> E, S = enumerate, sorted >>> l = [3,1,2,2,3] >>> [a for _,a in S((a,b) for b,(_,a) in E(S((a,b) for b,a in E(l))))] [3, 0, 1, 2, 4] 

Unutbu's answer is easier to read and generates less junk.

Answer 4

 k = [3, 0, 1, 2, 4] initial = dict(zip(k, range(len(k)))) #{0: 1, 1: 2, 2: 3, 3: 0, 4: 4} sorted_initial = dict(zip(sorted(k), range(len(k)))) #{0: 0, 1: 1, 2: 2, 3: 3, 4: 4} initial.update(sorted_initial) #{0: 0, 1: 1, 2: 2, 3: 3, 4: 4} result = [initial[i] for i in k] #[3, 0, 1, 2, 4] 

Answer 5

If you are doing statistical calculations, you will probably start using numpy at some point. With numpy, you can use the existing argsort implementation:

 >>> from numpy import array >>> x = array([3, 1, 2, 2, 3]) >>> x.argsort().argsort() array([3, 0, 1, 2, 4]) 

This is the exact version of unutbu's answer. A night click response can be implemented as

 >>> from numpy import array, empty_like, arange >>> x = array([3, 1, 2, 2, 3]) >>> s = x.argsort() >>> r = empty_like(s) >>> r[s] = arange(x.size) >>> r array([3, 0, 1, 2, 4])