如何找到逆置换？

Question

假设我有一个未知的向量v和一个置换p。

如何从v(p)和p重构出v?

等价的问题是找到一个置换q，使得p(q)=[1 2 ... n]？

由于这将在紧密的循环中运行，所以需要答案向量化（并且高效）。

- amit

Answer 1

我通常使用以下方法来找到逆排列：

[~,q] = sort(p);

比Divakar建议的方法更快。

- Jens Boldsen

---

显然，对数据进行排序并获取索引。简单，我来尝试一下。谢谢。 - amit

是的，这应该非常高效！ - Divakar

Answer 2

如果您想要数组 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*v == vp，其中适当的置换算子（矩阵）为 P = sparse(1:numel(p),p,1) 和 P^(-1)==P.'==sparse(p,1:numel(p),1)。因此得到相同的结果。

如果你在循环中使用这个，请确保在操作之前正确地将 q 或 v 重置为 []。如果 p 的长度发生变化，如果新的 p 比旧的 p 短，否则会得到错误的结果。

- knedlsepp

---

这可能很有趣，因为 OP 希望在紧密循环中运行它，以便 1:numel(P) 可以存储在向量中，并在该紧密循环中迭代使用！因此，这样可以更有效率。 - Divakar

这是一种聪明而快速的方法！但是，如果您将其放在循环中并且在某个时刻p获取较少的元素，则会遇到问题，但是如果之后添加类似于q=q(1:numel(p));的内容，它将被修复（并且仍然比我的方法更快）。 - Jens Boldsen

@JensBoldsen：是的，在此之前，q或v应为空，以使其正常工作。我将其添加到答案中以进行澄清。 - knedlsepp

请问您能否分享一下这里的幕后情况？ - amit

@amit：我添加了一些澄清。也许一个例子可以帮助澄清。 p(1:4) = [4,3,2,1]，逆置换可以定义为：q([4,3,2,1]) = 1:4。更具体地说，p：（4->1，3->2，2->3，1->4），而q：（4<-1，3<-2，2<-3，1<-4）。 - knedlsepp

Answer 3

使用 `ismember` -

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

使用intersect -

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

使用 `bsxfun` -

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

- Divakar

---

您能否提及这些函数的复杂性，以及运行此方法需要多少成本？（大O符号也可以）我的担忧是它将以二次时间运行，这对我来说不是一个选择。 - amit

@amit 你的 ndims(v) 是多少？ - Divakar

正如我所说，v 是一个向量，因此 ndims(v) = 2。 - amit

@amit.. 啊，你是不是指排列permute？基本上我假设你有一个多维数组v，你想用q作为维度数组来permute它的维度。我猜我在假设方面犯了一个错误？ - Divakar

@amit 我认为在那里使用numel(p)会更合适。已经进行了编辑。 - Divakar