8

我正在寻找一种重新排序技术来将邻接矩阵的连接组件组合在一起。

例如，我用蓝色和绿色两组做了一个插图。最初，'1' 的条目分布在矩阵的行和列中。通过对行和列重新排序，所有“1”都可以位于矩阵的两个连续部分中，从而更清楚地显示蓝色和绿色分量。

插图

我不记得这种重新排序技术叫什么了。我搜索了许多邻接矩阵、集团、排序和重新排序的组合。

我发现的最接近的热门歌曲是

  1. symrcm将元素移近对角线，但不组成组。

  2. 有没有办法重新排序矩阵的行和列以在 R 中创建一个密集的角落？它专注于删除完全空的行和列

请提供该技术的通用名称，以便我可以更有效地进行谷歌搜索，或者向我指出 Matlab 函数的方向。

4

1 回答 1

4

我不知道是否有更好的选择可以给你直接的结果，但这里有一种方法可以满足你的目的。

您的输入：

>> A

A =

 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1
 1     0     0     1     0
 0     1     1     0     1

方法一

将第一行和第一列分别作为 Column-Mask( maskCol) 和 Row-Mask( maskRow)。

获取哪些值在第一行和第一列中都包含值的掩码

maskRow = A(:,1)==1;
maskCol = A(1,:)~=1;

重新排列行（根据行掩码）

out = [A(maskRow,:);A(~maskRow,:)];

给出这样的东西：

out =

 1     0     0     1     0
 1     0     0     1     0
 0     1     1     0     1
 0     1     1     0     1
 0     1     1     0     1

重新排列列（根据列掩码）

out = [out(:,maskCol),out(:,~maskCol)]

给出期望的结果：

out =

 1     1     0     0     0
 1     1     0     0     0
 0     0     1     1     1
 0     0     1     1     1
 0     0     1     1     1

只需检查索引是否在它们应该在的位置，或者您是否想要相应的重新排列的索引；）

重新安排之前：

idx = reshape(1:25,5,[])

idx =

 1     6    11    16    21
 2     7    12    17    22
 3     8    13    18    23
 4     9    14    19    24
 5    10    15    20    25

重新安排后（与之前相同的过程）

outidx = [idx(maskRow,:);idx(~maskRow,:)];
outidx = [outidx(:,maskCol),outidx(:,~maskCol)]

输出：

outidx =

 2    17     7    12    22
 4    19     9    14    24
 1    16     6    11    21
 3    18     8    13    23
 5    20    10    15    25

方法二

对于Generic case，如果您事先不知道矩阵，这里是查找maskRow和的过程maskCol

使用的逻辑：

  1. 取第一排。将其视为列掩码 ( maskCol)。

  2. 对于第 2 行到最后一行，重复以下过程。

  3. 将当前行与maskCol.

  4. 如果任何一个值与 匹配maskCol，则找到元素明智的逻辑 OR 并将其更新为新的maskCol

  5. 重复这个过程直到最后一行。

  6. maskRow当列用于迭代时，查找的过程相同。

代码：

%// If you have a square matrix, you can combine both these loops into a single loop.
maskCol = A(1,:);
for ii = 2:size(A,1)
    if sum(A(ii,:) & maskCol)>0 
        maskCol = maskCol | A(ii,:);
    end
end

maskCol = ~maskCol;

maskRow = A(:,1);
for ii = 2:size(A,2)
    if sum(A(:,ii) & maskRow)>0 
        maskRow = maskRow | A(:,ii);
    end
end

这是一个尝试的示例：

%// Here I removed some 'ones' from first, last rows and columns.
%// Compare it with the original example.
A = [0     0     1     0     1
     0     0     0     1     0
     0     1     1     0     0
     1     0     0     1     0
     0     1     0     0     1];

然后，重复您之前执行的过程：

out = [A(maskRow,:);A(~maskRow,:)];        %// same code used
out = [out(:,maskCol),out(:,~maskCol)];    %// same code used

结果如下：

>> out

out =

 0     1     0     0     0
 1     1     0     0     0
 0     0     0     1     1
 0     0     1     1     0
 0     0     1     0     1

注意：这种方法可能适用于大多数情况，但在极少数情况下仍可能失败。

这里，是一个例子：

%// this works well.
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     1     0     0     1    1];

%// This may not
%// Second col, last row changed to zero from one
A = [0     0     1     0     1    0
     1     0     0     1     0    0
     0     1     0     0     0    1
     1     0     0     1     0    0
     0     0     1     0     1    0
     0     0     0     0     1    1];

为什么会失败？

当我们遍历每一行（以查找列掩码）时，例如，当我们移动到第三行时，没有一个列与第一行匹配（当前maskCol）。因此，第 3 行（第 2 个元素）携带的唯一信息丢失了。

这可能是罕见的情况，因为其他一些行可能仍包含相同的信息。见第一个例子。第三行的元素也没有与第一行匹配，但由于最后一行具有相同的信息（第二个元素为 1），因此它给出了正确的结果。只有在极少数情况下，可能会发生类似的情况。知道这个缺点仍然是件好事。

方法三

这是蛮力替代方案。如果您认为前一个案例可能会失败，则可以应用。在这里，我们使用while loopupdated 运行前面的代码（查找行和列掩码）次数maskCol，以便找到正确的掩码。

程序：

 maskCol = A(1,:);
 count = 1;
 while(count<3)
     for ii = 2:size(A,1)
         if sum(A(ii,:) & maskCol)>0
             maskCol = maskCol | A(ii,:);
         end
     end
     count = count+1;
 end

采用上一个示例（上一个方法失败的地方）并在有和没有的情况下运行while-loop

没有蛮力：

>> out

out =

 1     0     1     0     0     0
 1     0     1     0     0     0
 0     0     0     1     1     0
 0     1     0     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

使用蛮力 while 循环：

>> out

out =

 1     1     0     0     0     0
 1     1     0     0     0     0
 0     0     0     1     1     0
 0     0     1     0     0     1
 0     0     0     1     1     0
 0     0     0     0     1     1

获得正确结果所需的迭代次数可能会有所不同。但是有一个好数字是安全的。

祝你好运！

于 2015-05-29T17:06:48.980 回答