CODEWITHSUNDEEP
algorithmmatlabpermutation
amit
amit

Reputation: 178471

How to find the inverse permutation?

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

Upvotes: 5

Views: 2034

Answers (3)

knedlsepp
knedlsepp

Reputation: 6084

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.

Upvotes: 7

Divakar
Divakar

Reputation: 221584

With ismember -

[~,q] = ismember(1:numel(p),p)

With intersect -

[~,~,q] = intersect(1:numel(p),p)

With bsxfun -

[q,~] = find(bsxfun(@eq,[1:numel(p)],p(:)))

Upvotes: 2

Jens Boldsen
Jens Boldsen

Reputation: 1275

To find the inverse permutation I usually use:

[~,q] = sort(p);

Which is faster than the methods suggested by Divakar.

Upvotes: 8

Related Questions