如何找到逆排列？

Question

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

如何从 v(p) 和 p 重建 v？

一个等效的问题是找到一个排列 q 使得 p(q) = [1 2 ... n]?

由于这将运行进入一个紧密的循环，我需要将答案矢量化（并且高效）。

Answer 1

与ismember-

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

与intersect-

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

与bsxfun-

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

Answer 2

求逆排列我通常使用：

[~,q] = sort(p);

这比 Divakar 建议的方法更快。

Answer 3

如果您想要 p 的逆排列 q，它不会比：

更有效

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

因此，您可以通过以下方式从 vp = v(p) 和 p 重构 v：

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

甚至更快，无需显式构造 q:

v(p) = vp;

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

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

如何找到逆排列？

How to find the inverse permutation?

algorithm

matlab

permutation