CODEWITHSUNDEEP
pythonlistpython-3.xswapindices
PurkkaKoodari
PurkkaKoodari

Reputation: 6809

Swapping indices with values in a Python list?

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

Upvotes: 2

Views: 2173

Answers (4)

Nizam Mohamed
Nizam Mohamed

Reputation: 9220

This is very naive;

[ [ x[0] for x in enumerate(A) if x[1] == i][0] for i in range(len(A)) ]

This works perfect, 

[A.index(A.index(i)) for i in A]

This is better; 

[A.index(i[0]) for i in enumerate(A)]

This one beats the other;

[A.index(i) for i in range(len(A))]

Proof; 

import random as r
for l in [ r.sample(range(5),5) for n in range(5) ]:
    A = l
    B = [A.index(A.index(i)) for i in A]
    print "A is : ", A
    print "B is : ", B
    print "Are B's elements indices of A? : ", A == [B.index(B.index(i)) for i in B]
    print

Upvotes: 0

Andrey
Andrey

Reputation: 60065

A = [0, 4, 1, 3, 2]

B = [None]*len(A)

for i, x in enumerate(A):
    B[x] = i

print B

res: [0, 2, 4, 3, 1]

Upvotes: 0

Martijn Pieters
Martijn Pieters

Reputation: 1121834

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.

Upvotes: 4

bereal
bereal

Reputation: 34282

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).

Upvotes: 6

Related Questions