Find all lines of a matrix which have a matching pair of values

Question

Florent Hannard 2019-5-29

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/464654-find-all-lines-of-a-matrix-which-have-a-matching-pair-of-values

评论： Luna 2019-6-10

在 MATLAB Online 中打开

Hi everyone,

Given a matrix, I would like to find all pairs of lines which have a matching pair of values.

So for :

A = [1 2 3 4; 
5 7 8; 
5 7 9; 
6 7 13; 
8 13 15]

I would like to get a matrix with similar values :

Pairs = [5 7;
         4 7; 
         6 13]

And for which lines these values are found :

Index = [2 3; 
         3 4; 
         4 5]

In other words : intersection of A(Index(i,1),:) and A(Index(i,2),:) is Pairs(i,:)

One simple way to do it would be to use the intersect function :

for i=1:length(A(:,1))
    for j=i+1:length(A(:,1))
        intersect(A(i,:),A(j,:)) 
    end
end

But this is not efficient for a very large matrix A. Could someone suggest a more efficient way to do it ?

Thanks!

Florent

3 个评论
显示 1更早的评论隐藏 1更早的评论

Guillaume 2019-5-29

编辑：Guillaume 2019-5-29

What if a pair is common to more than two rows? How should Index be constructed in that case?

"But this is not efficient for a very large matrix A"

What is considered large in this context?

Florent Hannard 2019-5-29

编辑：Florent Hannard 2019-5-29

That's right thanks, but what I hope is to get rid of (at least) one of the loop (with something similar to ismember).

Large could be something like [500x10] or more, and I will need to perform this operation many times (which is why I am trying to optimize it).

EDIT : I know that a pair will never be common to more than two rows.

请先登录，再进行评论。

请先登录，再回答此问题。

Answer 1

Jan 2019-5-31

1
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/464654-find-all-lines-of-a-matrix-which-have-a-matching-pair-of-values#answer_377331

在 MATLAB Online 中打开

Sort the input array to avoid some overhead in intersect:

A = [1 2 3 4; 
     2 5 7 8; 
     4 5 7 9; 
     4 6 7 13; 
     6 8 13 15]
As = sort(A, 2);
nA = size(A, 1);
m  = nA * (nA - 1) / 2;
Pairs = zeros(m, 2);  % Pre-allocate!
Index = zeros(m, 2);
count = 0;
for i1 = 1:nA
    Ai1 = A(i1, :);
    for i2 = i1 + 1:nA
        match = ismembc(Ai1, A(i2, :));  % C-Mex function, undocumented
        if any(match)
            count           = count + 1;
            Pairs(count, :) = Ai1(match);
            Index(count, 1) = i1;
            Index(count, 2) = i2;
        end
    end
end
Pairs = Pairs(1:count, :);
Index = Index(1:count, :);

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Luna 2019-6-10

+1

请先登录，再进行评论。

Answer 2

Kevin Phung 2019-5-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/464654-find-all-lines-of-a-matrix-which-have-a-matching-pair-of-values#answer_377099

编辑：Kevin Phung 2019-5-29

在 MATLAB Online 中打开

A = [1 2 3 4; 2 5 7 8; 4 5 7 9; 4 6 7 13; 6 8 13 15];
Pairs = [5 7; 4 7; 6 13];
index =zeros(size(Pairs,1),1);
for i = 1:size(Pairs,1)
    loc = ismember(A,Pairs(i,:));
    index(i,:)=find(sum(loc,2)==numel(Pairs(i,:)))';
end

5 个评论
显示 3更早的评论隐藏 3更早的评论

Jan 2019-5-29

Pairs is wanted as output of the function.

Florent Hannard 2019-5-29

Indeed, Pairs and index are wanted as outputs and not just the location of already indentified paires.

请先登录，再进行评论。

Answer 3

Luna 2019-5-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/464654-find-all-lines-of-a-matrix-which-have-a-matching-pair-of-values#answer_377106

编辑：Luna 2019-5-29

在 MATLAB Online 中打开

Basically you can use this:

Finds the first row of the pairs' elements seperately as logical indexes. Then adds them together.

If it matches at the same time on that row, sum of rows will be 2. So these are your new indexes that are found. Repeats them for 2nd and 3rd row also.

IndexesNew = zeros(size(Pairs,1),2); 
for i = 1:size(Pairs,1)
    IndexesNew(i,:) =  find(sum(ismember(A,Pairs(i,1)) + ismember(A,Pairs(i,2)),2) == 2)';
end

1 个评论
显示 -1更早的评论隐藏 -1更早的评论

Florent Hannard 2019-5-29

Thank you but this is not what I need.

Pairs and index are wanted as outputs and not just the location of already indentified paires.

请先登录，再进行评论。

Answer 4

Guillaume 2019-5-29

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/464654-find-all-lines-of-a-matrix-which-have-a-matching-pair-of-values#answer_377119

在 MATLAB Online 中打开

I don't see how you can avoid doing size(A, 1) * (size(A, 1)-1) / 2 comparisons of the rows one way or another. The problem with using intersect in a loop is that you're repeatedly sorting the rows that you may already have sorted previously so certainly taking that out of the loops would be useful.

The following may or may not be faster than using intersect in a loop. I haven't tested.

%If size(A, 1) is fixed, this part can be precomputed before applying the rest to each A
%It simply precomputes row indices for comparison
[row2, row1] = ndgrid(1:size(A, 1));
row1 = nonzeros(tril(row1, -1));
row2 = nonzeros(tril(row2, -1));
%finding pairs and locations
[uA, ~, destcol] = unique(A);   %only one call to unique on the whole matrix
hasnumber = zeros(size(A, 1), numel(uA)); %columns of hasnumber correspond to values in uA, rows to rows of A. Will contain one when the corresponding row contains uA
hasnumber(sub2ind(size(hasnumber), repmat(1:size(A, 1), 1, size(A, 2))', destcol)) = 1;
ismatch = hasnumber(row1, :) + hasnumber(row2, :) == 2;  %find which numbers are common to both row1 and row2 
haspair = sum(ismatch, 2) == 2;   %pair when exactly two numbers are common
uA = repmat(uA, 1, sum(haspair));
RowIndices = [row1(haspair), row2(haspair)]  %indices of row that have a matching pair
PairValues = reshape(uA(ismatch(haspair, :)'), 2, []).' %Actual values of pair