How to find the inverse permutation?

Question

Suppose I have an unknown vector v, and a permutation p.

How can I reconstruct v from v(p) and p?

An equivalent question would be to find a permutation q such that p(q) = [1 2 ... n]?

Since this is going to run in a tight loop, I need the answer to be vectorized (and efficient).

Answer 1

To find the inverse permutation I usually use:

[~,q] = sort(p);

Which is faster than the methods suggested by Divakar.

Answer 2

If you want the inverse permutation q of p, it won't get more efficient than:

q(p) = 1:numel(p);

You can thus reconstruct v from vp = v(p) and p via:

q(p) = 1:numel(p);
v = vp(q);

or even faster without explicitly constructing q:

v(p) = vp;

(You might have noticed that v = vp(q) corresponds to v == P^(-1)*vp and v(p) = vp corresponds to P*v == vp for appropriate permutation operators (matrices) P = sparse(1:numel(p),p,1) and P^(-1)==P.'==sparse(p,1:numel(p),1). Thus yielding the same result.)

If you use this in a loop, do however mind to properly reset q or v respectively to [] before this operation. In case of changing length of p, you would otherwise get wrong results if the new p was shorter than the old p.