(No, this is not a homework assignment nor a contest, even though it might look like one.)
I have a list A in Python that contains the numbers range(0, len(A)). The numbers are not in order, but all of them exist in the list.
I'm looking for a simple way to build a list B where the indices and values have been swapped, i.e. a list that, for each integer n, contains the position of n in A.
Example:
A = [0, 4, 1, 3, 2]
B = [0, 2, 4, 3, 1]
I can put the code to generate B either separately or in the code that generates A. In particular, here's how I generate A:
A = [value(i) for i in range(length)]
What would be the best way to do this?
Using the enumerate() function to decorate each value with their index, sorting with sorted() on the values, and then un-decorate again to extract the indices in value order:
[i for i, v in sorted(enumerate(A), key=lambda iv: iv[1])]
This has a O(NlogN) time complexity because we used sorting.
Demo:
>>> A = [0, 4, 1, 3, 2]
>>> [i for i, v in sorted(enumerate(A), key=lambda iv: iv[1])]
[0, 2, 4, 3, 1]
We can also use a pre-built list to assign indices to for a O(N) solution:
B = [0] * len(A)
for i, v in enumerate(A):
B[v] = i
Demo:
>>> B = [0] * len(A)
>>> for i, v in enumerate(A):
... B[v] = i
...
>>> B
[0, 2, 4, 3, 1]
This is probably the better option if time complexity is of a big issue; for N = 100 the sorting approach will take about 461 steps vs. 100 for the pre-built list approach.