CODEWITHSUNDEEP
matlabmatrixmatrix-multiplication
esem
esem

Reputation: 173

Find the indices of elements of matrix that form the maximum product

I have a task to find the maximum product of elements in a matrix. The input arguments are the matrix and the scalar n that tells me how many elements to multiply. If n=2, then I should multiply two by two. The maximum product can lie either in rows, or in columns on in diagonal. For example in this case A's elements were multiplied 2 by 2 along rows (B) and columns (C).

A =
   8     1     6
   3     5     7
   4     9     2
B =
      8.0000    6.0000
     15.0000   35.0000
     36.0000   18.0000
C =
     24.0000    5.0000   42.0000
     12.0000   45.0000   14.0000

I do it using the loop

    c=[]
for ii = 1:(length(A)-n+1)
    p = prod(A(:,ii:ii+n-1));
    c=[c p];
end

or 

for i=1:size(A,2)
      B(i,:)=real(exp(conv(log(A(i,:)),ones(1,n),'valid')));
      C(:,i)=real(exp(conv(log(A(:,i)),ones(1,n),'valid')));
end

In both cases I receive the product but when it comes to getting the maximum among that products, (in my case that is the product of A(2,2)*A(3,2)=45) I cannot find the indices of original matrix elements that formed that product, i.e. (2,2) and (3,2).

Any help will be appreciated.

Upvotes: 1

Views: 199

Answers (2)

Dave
Dave

Reputation: 460

The information can be worked out from knowing where, in B or C, the maximum value occurs. This is returned by the max function as a second argument, albeit in index form. I've tried out your code for producing B and C, and it doesn't seem to produce what you've got, HOWEVER, assuming that you've got some way of producing B and C as in the first part of your question, the following code will return (r1,c1) and (r2,c2) the reference to the two multiplicands (assuming that there is only one maximum - you really do need to check for this):

[maxB,IB]=max(B(:));
[maxC,IC]=max(C(:));
if (maxB>maxC)
    [r1,c1]=ind2sub(size(B),IB);
    r2=r1; c2=c1+n-1;
else
    [r1,c1]=ind2sub(size(C),IC);
    r2=r1+n-1; c2=c1;
end

I'm not quite sure whether n is a distance, in which case:

B=A(:,1:end-n+1).*A(:,n:end);
C=A(1:end-n+1,:).*A(n:end,:);

or whether you mean to take the product of all terms within n of the starting point. Either way, the maximum can be found using the above code.

Upvotes: 1

Ian Riley
Ian Riley

Reputation: 523

Given inputs A and n, and assuming you don't care which output you give in case of a tie,

%Setup
[r, c] = size(A)
if r <= n
    maxProd = prod(A(1:n,1),1);
elseif c <= n
    maxProd = prod(A(1,1:n),2);
else 
    return
end

indOut = zeros(n, 2);
dirOut = 0;

%Check verticals 
for ii = 1:(r-n+1)
    for jj = 1:c
         testProd = prod(A(ii:ii+n-1,jj),1);
         if testProd > maxProd
             maxProd = testProd;
             indOut(1,:) = [ii jj];
             dirOut = 1;
         end
    end
end

%Check horizontals
for ii = 1:r
    for jj = 1:(c-n+1)
         testProd = prod(A(ii,jj:jj+n-1),2);
         if testProd > maxProd
             maxProd = testProd;
             indOut(1,:) = [ii jj];
             dirOut = 2;
         end
    end
end

%Set output
for ii = 2:n
    if dirOut == 1;
        indOut(1,n) = indOut(1,n-1) + 1;
    else
        indOut(2,n) = indOut(2,n-1) + 1;
    end
end

If you do care about ties, you'll have to add additional outputs to the side of the indOut matrix

Upvotes: 1

Related Questions