## Compare each row of matrix with the rest, conditionally

on 30 Dec 2018
Latest activity Commented on by Oskar Larsson

on 2 Jan 2019

### per isakson (view profile)

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!

R2017b

### per isakson (view profile)

on 31 Dec 2018
Edited by per isakson

### per isakson (view profile)

on 1 Jan 2019

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

Show 1 older comment
per isakson

### per isakson (view profile)

on 31 Dec 2018
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.
per isakson

### per isakson (view profile)

on 1 Jan 2019
[ ~, ix ] = sort( M3(:,1), 'ascend' );
M3 = M3( ix, : );
and
M3 = sortrows( M3, 1, 'ascend' );
do the same thing, but sortrows is slower.

on 2 Jan 2019
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!