Compare each row of matrix with the rest, conditionally

Dear MathWorks Community,

I have written a short script that generates a matrix containing the lengths of the sides of right triangles, where all lengths are integers (e.g. the 3-4-5-triangle). After generation, the matrix is sorted by rows, so that any triangles with the same legs are removed (e.g. 3-4-5 is considered equal to 4-3-5), sides of the triangle are ordered by descending length (e.g. 3-4-5 becomes 5-4-3), and the rows are ordered in ascending order, by first column. See code-snippet # 2 below. Code-snippet # 2 is executed before code-snippet # 1.

My question is: How can I remove any triangles that are congruent from the resulting list? Preferably by removing the larger congruent triangles and keeping the smaller (e.g. remove 6-8-10 and keep 3-4-5).

I have tried doing the following, with limited succes: (code-snippet # 1)

for l = 1 : 1 : size(K1,1) 
% Go through l from 1 to the number of rows in matrix K1, in steps of 1.
    for m = 1 : 1 : size(K1,1)
% Go through m from 1 to the number of rows in matrix K1, in steps of 1.
        leg1L = K1(l,2);
% Variable leg1L is the 1st leg of the triangle described in K1 on row l.
        leg2L = K1(l,3);
% Variable leg2L is the 2nd leg of the triangle described in K1 on row l.
        leg1M = K1(m,2);
% Variable leg1M is the 1st leg of the triangle described in K1 on row m.
        leg2M = K1(m,3);
% Variable leg2M is the 2nd leg of the triangle described in K1 on row m.
        frac1 = leg1L/leg1M;
% Variable frac1 is:
% the 1st leg of the triangle described in K1 on row l,
% divided by 
% 1st leg of the triangle described in K1 on row m.
        frac2 = leg2L/leg2M;
% Variable frac2 is:
% the 2nd leg of the triangle described in K1 on row l,
% divided by 
% the 2nd leg of the triangle described in K1 on row m.
        if ( (l ~= m) && (frac1 == int64(frac1)) && (frac2 == int64(frac2)) )
% IF l is not equal to m AND frac1 is an integer AND frac2 is an integer.
        K2(l,:) = [0 0 0];
% Row l of K2 equals zeroes.
        K2(m,:) = [0 0 0];
% and row m of K2 equals zeroes.
        elseif ( (l ~= m) && (frac1 ~= int64(frac1)) && (frac2 ~= int64(frac2)) )
% IF l is not equal to m AND frac1 is not an integer AND frac2 is not an integer.
            K2(m,:) = K1(m,:);
% Row m of K2 equals row m of K1.
        end
    end
end

It removes 3-4-5, 5-12-13 and 75-100-125, which is correct, but not entirely the desired result, as the first two of these sets are smaller than e.g. 6-8-10 and 10-24-26. It also fails to remove many congruent triangles, e.g. 12-16-20, which is simply 2*(6-8-10).

The code for generating, sorting and ordering the matrix is as follows, code-snippet # 2:

K = zeros(1e4,3);
% Matrix for combination is allocated, to speed up for-loops.
 
k = 0;
% Loop-counter is allocated.
for b = 1:1:100
% Go through b from 1 to 100 in steps of 1.
    for c = 1:1:100
% Go through c from 1 to 100 in steps of 1.
        a = sqrt(b^2 + c^2);
% a is defined as the squareroot of the sum of the squares of b and c.
        if ( a == int64(a) )
% If a equals the integer of a
            k = k+1;
% Add 1 to the loop-counter k
            K(k,:)=[a, b, c];
% And write a, b and c to the k'th line of matrix K.
        end
    end
end
 
K = K(any(K,2),:);
% Remove any zero-rows of matrix K.
 
K = sortrows(K,1);
% Sort rows of matrix K by descending order after the values in the first
% column (the hypotenuse).
 
K1 = (zeros(size(K)));
% Allocate a zero-matrix the size of K called K1, for manipulating data
% from K.
% The purpose is to remove any copy-rows, where c and by have simple
% swapped places, so that 5 = sqrt(3^2 + 4^2) will be seen as equal to 
% 5 = sqrt(4^2 + 3^2).
 
for i = 1 : 1 : size(K,1)
% Go through i from 1 to the number of rows in matrix K, in steps of 1.
vec = K(i,:);
% The vector vec equals the i'th row of matrix K.
vec = sort(vec,'descend');
% The vector vec is sorted in descending order.
K1(i,:) = vec;
% The i'th row of K1 equals vec. The loop continues to the next number,
% until it has gone through all of the rows of matrix K.
end
 
K1 = unique(K1,'rows');
% Any rows in matrix K1 that are identical, are now removed.

The entire script can be found in the attachment. Note that it is slightly different; in this post I have removed some non-essential code for clarity.

Thank you for your help, and may you have a Happy New Year!

Answer 1

[per isakson]

Assumptions:

1. The lengths of the sides are whole numbers
2. The maximum length of the sides is "reasonable"

Another approach

%%
M = K1; 
angles = atan( M(:,3)./M(:,2) );
%%
[ ~, ixa, ixc ] = uniquetol( angles, eps(100) );
%%

The answer is in ixa and ixc. The tolerance, eps(100), is just my first guess. The value of the M(:,1) lets you pick the smallest congruent triangle. (Lämnas som övning ;-)

A complete script (in response to commemnt)

%% Grab a small sample 
M = K1(1:5,:);
M = flip( M, 1 );
%%
angles = atan( M(:,3)./M(:,2) );
%%
[ ~, ixa, ixc ] = uniquetol( angles, eps(100) );
%
%% "unique triangles"
M1 = M(ixa,:);
%
%% Replace rows by the smallest congruent triangle
for jj = 1 : length( ixa )
    ix_congruent = find( ixc(ixa(jj)) == ixc );
    if length( ix_congruent ) >= 2
        [ ~, ix ] = min( M(ix_congruent,1) );
        M1(jj,:) = M( ix_congruent(ix), : );
    end
end
%% Order the triangles by the length of the hypotenuse
[ ~, ix ] = sort( M1(:,1), 'ascend' ); 
M2 = M1( ix, : );

Inspect the result

>> M
M =
    17    15     8
    15    12     9
    13    12     5
    10     8     6
     5     4     3
>> M2
M2 =
     5     4     3
    13    12     5
    17    15     8
>> 

The first five rows of K1 contain three "unique" triangles

Another variant, which uses uniquetol( ____, 'OutputAllIndices',true )

function    M3 = variant2( M )
    %%
    cosx = M(:,3)./M(:,1);
    [ ~, ixa, ~ ] = uniquetol( cosx, eps(100), 'OutputAllIndices',true );
    %%
    len = length( ixa );
    M3  = nan( len, 3 );
    for jj = 1 : len
        if length( ixa{jj} ) >= 2
            [ ~, ix ] = min( M([ixa{jj}],1) );
            M3(jj,:)  = M( ixa{jj}(ix), : );
        else
            M3(jj,:)  = M( ixa{jj}, : );
        end
    end
    M3 = sortrows( M3, 1, 'ascend' );
end

A last variant that relies on that uniquetol returns the first occurence of a repeated value. Thus by first sorting with respect to the hypotenuse there is no need compare the hypotenuse of the equal values

function    M3 = variant3( M )
    %%
    [ ~, ix ] = sort( M(:,1), 'ascend' );
    M = M( ix, : );
    %%
    cosx = M(:,3)./M(:,1);
    [ ~, ixa, ~ ] = uniquetol( cosx, eps(100) );
    %%
    M3  = M( ixa, : );
    [ ~, ix ] = sort( M3(:,1), 'ascend' );
    M3 = M3( ix, : );
end

[Oskar Larsson]

Hi Per,

Thank you for your reply, or should I say tack så mycket ;)! Your assumptions are correct, as is the tolerance, which could probably be set to zero, if round-off errors were not present. The idea of using a single tangent-calculation instead of the double fractions I used is great!

However, I'm not quite sure that I understand the output of this line:

[ ~, ixa, ixc ] = uniquetol( angles, eps(100) );

What is it that I am presented with in the resulting ixa and ixc vectors?

Again, thank you very much for your time!

Edit: I have read the reference-page for uniquetol, (and eps(x) ), but I'm afraid that it didn't make things clearer for me.

[per isakson]

There are many people at The MathWorks working on the documentation and I'm sure they do their best. ... . It takes some exercises to become comfortable with this level of indexing. Step through my code in debug mode and inspect all intermediate values.

See: Debug a MATLAB Program and Examine Values While Debugging

[per isakson]

[ ~, ix ] = sort( M3(:,1), 'ascend' );
M3 = M3( ix, : );

and

M3 = sortrows( M3, 1, 'ascend' );

do the same thing, but sortrows is slower.

[Oskar Larsson]

Thank you very much Per, for your detailed and varied answers. What I ended up using, heavily inspired by your approaches, is this (after a matrix K1 as in my first post is generated):

K2 = K1;
% Allocate matrix K2 for speed.
zerocolK2 = zeros(size(K1,1),1);
% create zero vector (column) with the same number of rows as K1, 1 column.
K2 = cat(2,K2,zerocolK2);
% Concatenate zero column to K2.
 
for l = 1 : 1 : size(K1,1) 
% Go through l from 1 to the number of rows in matrix K1, in steps of 1.
        leg1L = K1(l,2);
% Variable leg1L is the 1st leg of the triangle described in K1 on row l.
        leg2L = K1(l,3);
% Variable leg2L is the 2nd leg of the triangle described in K1 on row l.
        frac1 = leg1L/leg2L;
% Variable frac1 is:
% the 1st leg of the triangle described in K1 on row l,
% divided by 
% 2nd leg of the triangle described in K1 on row l.
        K2(l,4) = frac1;
% Row l, column 4 of K2 equals zeroes.
end
 
% To eliminate congruent triangles:
% Add a 4th column, consisting of the fraction (L1/L2)
% for legs 1 and 2 in a triangel (row).
% Use unique to filter any rows that share the same 4th value.
[~, IA, ~] = unique(K2(:,4));
% Finds the unique values of column 4 in K2, for each row. IA is the
% index-vector for the unique values.
K3 = K2(IA,:);
% K3 is every indexed row from  K2 with a unique value in the fourth
% column.
K3 = sortrows(K3,1);
% K3 is sorted in ascending order based on the values of the first column.
K3(:,4) = [];
% The fourth column is deleted.

Which graphically results in this:

If the full code would interest you, or anyone else, I have attached the final file to this post.

Again - many thanks for most valuable help!