如何找到逆置换？

Question

假设我有一个未知的向量v和一个排列p.

我怎样才能重建v的v(p)和p？

一个同等的问题是找到一个q这样的排列p(q) = [1 2 ... n]？

由于这将在一个紧密的循环中运行,我需要回答是矢量化(和高效).

Answer 1

为了找到我通常使用的逆置换:

[~,q] = sort(p);

这比Divakar建议的方法更快.

Answer 2

如果你想逆置换q的p，也不会获得比更有效：

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

你可以这样重建v的vp = v(p)，并p通过：

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

甚至在不显式构造的情况下更快q：

v(p) = vp;

（您可能已经注意到v = vp(q)对应v == P^(-1)*vp和v(p) = vp对应P*v == vp于适当的置换运算符（矩阵）P = sparse(1:numel(p),p,1)和P^(-1)==P.'==sparse(p,1:numel(p),1)。因此产生相同的结果。）

如果您在循环中使用它，请注意在此操作之前正确重置q或v分别为[]。在改变长度的情况下，p如果新的p比旧的短，你会得到错误的结果p。