arrays - 基于等价性将值分组在一起

Question

我有一个 Nx2 矩阵(在本例中为 6X2)，如下所示:

5  4
8  6
9  8 
10 9
15 14
16 15

我想按以下方式对它们进行分组:

*(5,4) 是第一组。它与剩余的行一起检查。由于 5 和 4 都没有出现在剩余的行中，因此可以保留原样。

*(8,6) 是下一组。然而在第 3 行 8 再次出现为 (9,8)。所以它连接到第 2 组，即第 2 组变为 (8,6,9,8)。

*看到下一个(10,9)。但是9属于第2组，10也被添加了。所以第二组现在是 (8,6,9,8,10,9)。

*下一个 (15,14) 可见。到目前为止，它还没有出现或重复。所以它成为第 3 组即 (15,14)。

*最后，(16,15) 被看到了。但由于 15 在第 3 组中重复出现，该组现在更新为 (15,14,16,15)。

最后可以使用MATLAB中的unique命令来去除组中的冗余元素。

我希望最终输出为组数:

5   4
8   6   9   10
15  14  16

注意:行组中元素的顺序并不重要，因为 (5,4) 或 (4,5) 是相同的。我也猜想，最终输出可能会附加零，以使其成为一个等维矩阵，即

5   4   0   0 
8   6   9  10 
15 14  16   0

请帮忙。谢谢。

Answer 1

所以，我觉得应该有一种方法可以使用基于树的算法或不相交集/联合查找类型的方法来做到这一点。但是对于可能不是那么有效的肮脏的第一种方法，我编写了以下代码:

A = [5 4
     8 6
     9 8     
    10 9
    15 14
    16 15
     8 8
     3 4
     3 1
     ];
B = mat2cell(A,ones(size(A,1),1),2);

iter = 1;
while(true)
    if (iter > size(B,1))
        break
    end
    y = B{iter};
    C = cat(1,false(iter,1),cellfun(@(x) any(sum(bsxfun(@eq,x,y'))),B(iter+1:end)));
    if any(C)
        B{iter} = (cat(2,B{iter}, B{C}));
        % or put you can start shortening them here, by calling unique() already:
        %B{iter} = unique(cat(2,B{iter}, B{C}));
        B(C) = [];
    else
        iter = iter+1;
    end
end

B = cellfun(@unique,B,'uni',false);
B{:}

效果还不错。我不知道这是否能满足您的需求，但快速编写代码很有趣。感谢这个有趣的问题。