I need to get the indexes of all diagonals in a matrix. The matrix can be non square.
The diag function gives the values, but I need the coords. So for instance with this: [1 2 3; 4 5 6; 7 8 9], I want [1 1; 2 2; 3;3] PLUS [2 6] and 3 because they are the upper diagonals of the matrix, and same for below i.e. [4 8] and 7. So the full list of indexes is: [1 1; 2 2; 3 3], [1 2; 2 3], [1 3], [2 1], [3 2], [3 1].
And I need this in the other diagonal direction too...
And it needs to work for matrices of any shape i.e. not just square ones, including vectors (i.e. 1xn and nx1) - but I guess I can test for these last 2 cases and treat separately.
EDIT: An example of a non square matrix is this 3x2 one:
1 2
3 4
5 6
In this case, the indexes I need are:
[1 1; 2 2]
[2 1; 3 2]
[1 2]
[3 1]
And then the same for diagonals running the other way...
I am aware of the diag function and can write a bit of code to iterate over the matrices, but I can't then see how to easily turn those values into indexes.
As for why I need this: It's an online course I'm doing in MatLab. An introduction to programming, using MatLab. I'm a reasonably experienced programmer but I'm not familiar with MatLab and I want to learn it more.
The question asks us to find the biggest product of any n numbers in any direction, i.e. rows, cols, and diagonals (both ways). And the thing is we don't return the product, we return the indexes of the elements making up this product.
I hope this provides more information.
EDIT 2: Sorry for not getting back to you guys, I've been very busy doing other things. When I first posted here, I assumed I was missing something and this would be something that took a few lines. But it's trickier than that, so the code you guys are posting will take me a little more time to go through and understand etc. But I hope to do this today and accept one as an answer. Thanks for all the replies.
Ok, so I coded this up myself last night. It's very long and I'm sure it can be done in better ways. I don't know MatLab well, so my solution is pretty naive. But it works.
function indicies = maxproduct(A, n)
function diagIndicies = getAllReverseDiagonalIndicies()
% This function returns lists of indicies in the reverse diagonal direction (top-right to bottom-left)
if rows == 1
numCells = 0;
for j=1:length(A)
temp = [1, j];
numCells = numCells + 1;
diagIndicies{numCells} = temp;
end
return
end
% This loop adds all diagonals down and to the right, to the end of the matrix.
%fprintf('Diagonals down to main one are:\n');
numCells = 0;
for x=1:rows
rowNum = x;
colNum = 1;
temp = [];
while rowNum >= 1 && rowNum <= rows && colNum <= cols
temp = [temp; [rowNum colNum]];
rowNum = rowNum - 1;
colNum = colNum + 1;
end
numCells = numCells + 1;
temp = flipud(temp); % Need row major order for assignment
%disp(temp);
diagIndicies{numCells} = temp;
end
% Now go along bottom row
%fprintf('Diagonals along bottom are:\n');
for y=2:cols
rowNum = rows;
colNum = y;
temp = [];
while rowNum >= 1 && colNum <= cols
temp = [temp; [rowNum colNum]];
rowNum = rowNum - 1;
colNum = colNum + 1;
end
numCells = numCells + 1;
temp = flipud(temp); % Need row major order for assignment
%disp(temp);
diagIndicies{numCells} = temp;
end
end
function diagIndicies = getAllDiagonalIndicies()
% This function returns lists of indicies in the main diagonal direction (top-left to bottom-right)
if rows == 1
numCells = 0;
for j=1:length(A)
temp = [1, j];
numCells = numCells + 1;
diagIndicies{numCells} = temp;
end
return
end
% This loop adds all diagonals down and to the left, to the lhs of the matrix.
%fprintf('Diagonals down to main one are:\n');
numCells = 0;
for x=1:rows
rowNum = x;
colNum = cols;
temp = [];
while rowNum >= 1 && rowNum <= rows && colNum >= 1
temp = [temp; [rowNum colNum]];
rowNum = rowNum - 1;
colNum = colNum - 1;
end
numCells = numCells + 1;
temp = flipud(temp); % Need row major order for assignment
%disp(temp);
diagIndicies{numCells} = temp;
end
% Now go along bottom row...
%fprintf('Diagonals along bottom are:\n');
for y=cols-1:-1:1
rowNum = rows;
colNum = y;
temp = [];
while rowNum >= 1 && colNum >= 1
temp = [temp; [rowNum colNum]];
rowNum = rowNum - 1;
colNum = colNum - 1;
end
numCells = numCells + 1;
temp = flipud(temp); % Need row major order for assignment
%disp(temp);
diagIndicies{numCells} = temp;
end
end
% Main function starts here.
[rows, cols] = size(A);
theMaxProduct = -10000000;
indicies = [];
if isscalar(A)
if A == 1 && n == 1
indicies = [1,1];
return;
else
return;
end
end
% Find max product in each row of A
for i=1:rows
for j=1:cols-n+1
theProduct = 1;
for k=j:j+n-1
theProduct = theProduct * A(i, k);
end
if theProduct > theMaxProduct
theMaxProduct = theProduct;
indicies = [];
for k=j:j+n-1
indicies = [indicies; [i, k]];
end
end
end
end
fprintf('theMaxProduct after examining rows = %15.15f\n', theMaxProduct);
% Find max product in each column of A
for i=1:cols
for j=1:rows-n+1
theProduct = 1;
for k=j:j+n-1
theProduct = theProduct * A(k, i);
end
if theProduct > theMaxProduct
theMaxProduct = theProduct;
indicies = [];
for k=j:j+n-1
indicies = [indicies; [k, i]];
end
end
end
end
fprintf('theMaxProduct after examining cols = %15.15f\n', theMaxProduct);
% Find max product along reverse diagonals of A
diagIndicies = getAllReverseDiagonalIndicies();
%disp(diagIndicies);
for i=1: length(diagIndicies)
[numIndicies, ~] = size(diagIndicies{i});
for j=1:numIndicies-n+1
theProduct = 1;
for k=j:j+n-1
theProduct = theProduct * A(diagIndicies{i}(k, 1), diagIndicies{i}(k, 2));
end
if theProduct > theMaxProduct
theMaxProduct = theProduct;
indicies = [];
for k=j:j+n-1
indicies = [indicies; [diagIndicies{i}(k, 1), diagIndicies{i}(k, 2)]];
end
end
end
end
fprintf('theMaxProduct after examining reverse diag = %15.15f\n', theMaxProduct);
% Find max product along diagonals of A
diagIndicies = getAllDiagonalIndicies();
%disp(diagIndicies);
for i=1: length(diagIndicies)
[numIndicies, ~] = size(diagIndicies{i});
for j=1:numIndicies-n+1
theProduct = 1;
for k=j:j+n-1
theProduct = theProduct * A(diagIndicies{i}(k, 1), diagIndicies{i}(k, 2));
end
if theProduct > theMaxProduct
theMaxProduct = theProduct;
indicies = [];
for k=j:j+n-1
indicies = [indicies; [diagIndicies{i}(k, 1), diagIndicies{i}(k, 2)]];
end
end
end
end
fprintf('theMaxProduct after examining main diag = %15.15f\n', theMaxProduct);
end