如何在Matlab中找到2-D矩阵置换后的映射

Question

我有两个二维矩阵A和B，其中B是通过对A进行（按行）排列得到的。 A中有一些重复的记录（因此在B中也有）。 我想找到生成B的映射关系。 我正在使用Matlab。 对我来说，只需要一个解决方案。

示例：

A = [ 2 3 4; 4 5 6; 2 3 4];
B = [ 4 5 6; 2 3 4; 2 3 4];

映射关系如下：

p = [3 1 2]   // I want this mapping, however the solution p= [2 1 3] is also correct and acceptable

在Matlab中，A = B(p,:) 表示取矩阵B中第p行的所有列，并将其赋值给矩阵A。

祝好

- remo

---

你是如何生成 B 的？ - Shai

我自己不会生成B，但我知道它是通过对A中的记录进行排列组合而生成的。 - remo

你能访问它的排列方式吗？ - Shai

不，这对我来说并不重要。我只需要排列，即上面例子中的p。 - remo

是的，那是个错误。我已经编辑了问题。谢谢。 - remo

Answer 1

先摘下低垂的果实。
假设没有重复行：

 % compute the permutation matrix
 P = all( bsxfun( @eq, permute( A, [1 3 2]),permute(B,[3 1 2]) ), 3 );
 [~, p] = max(P, [], 2 ); % gives you what you want

如果有重复项，我们需要在P的行/列中“打破平局”：

 n = size(A,1);
 bt = abs( bsxfun(@minus, 1:n, (1:n)' ) )/n; %//'
 [~, p] = max( P+bt, [], 2 );

- Shai

---

+1：不错的解决方案。我建议在处理浮点数值时使用公差。 - Eitan T

@EitanT 感谢您添加了我忘记的 bsxfun ;-）它真的很有趣！ - Shai

请注意，记录数量可能很多（例如，在13维中有1000个记录）。我认为这种方法不适用于大型数据集！然而，我无法完全理解你的代码。 - remo

@RezaMortazavi (1) 当 n 增长时，代码将会受到影响。尽管如此，我相信它仍能处理 n=O(1000) 的情况。(2) 你是否理解了没有重复的简单情况？ - Shai

是的，谢谢你的帮助。我也正在寻找一个基于kd树的解决方案，它在knnsearch中得到了实现，但重复记录再次成为了问题。你认为我可以将其用于这种情况吗？ - remo

如果你对我的解决方案的复杂性感到担忧，你可能想考虑一下Peter的答案，它似乎对于这个问题是O(nlogn)而不是O(n^2)。 - Shai

Answer 2

既然我们知道A和B总是有相同的行数，让我们寻找一种转换方式将它们转换为相同的标识形式。那么用sort怎么样？

[As, Ai] = sortrows(A);
[Bs, Bi] = sortrows(B);

现在有A(Ai,:) == B(Bi,:)，我们需要做的就是找到与Ai相匹配的Bi索引。Bi是正向映射，而Ai是反向映射。因此：

p = zeros(size(A,1),1);
p(Ai) = Bi;

抱歉，我只能理解英文和部分其他语言。如果您有需要翻译的英文内容，请告诉我，我会尽力帮助您。

- Peter

Answer 3

这里提供了一种使用sort()解决需要生成所有排列的问题的解决方案。

思路是对A和B进行排序，这将产生相同的排序矩阵。现在可以通过使用产生两个排序矩阵的索引IA和IB来找到排列。

A = [ 2 3 4; 4 5 6; 2 3 4];
B = [ 4 5 6; 2 3 4; 2 3 4];

[CA,IA]=sort(A,1)
[CB,IB]=sort(B,1)

idxA = IA(:,1)
idxB = IB(:,1)

[~, idxB_inverse] = sort(idxB)

idxA(idxB_inverse)

- user1884905