Swapping indices with values in a Python list?

Question

(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?

Answer 1

How about assigning to the pre-allocated B:

>>> A = [0, 4, 1, 3, 2]
>>> B = [0] * len(A)
>>> for k, v in enumerate(A): B[v] = k
>>> B
[0, 2, 4, 3, 1]

That would be O(n).

Answer 2

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.