Help finding best submatrix

This is a discussion on Help finding best submatrix within the C Programming forums, part of the General Programming Boards category; Hi everybody, i've got an assignment for thursday that i really cant work out, the exercise asks to find the ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65

    Help finding best submatrix

    Hi everybody, i've got an assignment for thursday that i really cant work out, the exercise asks to find the best submatrix of a given matrix of nr rows and nc columns through a function int bestsubmatrix(int nr, int nc, double S[nr][nc], double m) that has to return the biggest submatrix of S[nr][nc] where the average of its elements doesnt have to exceed the value of m, example:

    nr = 5, nc = 4, m = 2.6
    matrix[nr][nc] = {
    { 5.69, 1.42, 2.70, 2.17 },
    { 2.07, 4.01, 2.78, 2.88 },
    { 6.84, 2.94, 2.96, 1.85 },
    { 1.83, 1.76, 5.64, 5.51 },
    { 6.31, 5.50, 4.26, 6.10 }
    };
    the function has to return 6, in fact 2.70 + 2.17 + 2.78 + 2.88 + 2.96 + 1.85 / 6 = 2.55 < m
    till now thats what i was able to write:
    Code:
    void bestsubmatrix(int nr, int nc, double S[nr][nc], double m)
    {
    	int i, j, hold;
    	double sum = 0;
    	
    	for(i = 0; i < nr; i++)
    	{
    		for(j = 1; j < nc; j++)
    		{
    			sum = sum + S[i][j] + S[i][j - 1];
    			if(sum / (j + 1) <= m)
    			{
    				hold = j;				
    				printf("holding the %dth element of the row = %.2f\n", hold, S[i][hold]);
    			}
    			else
    			{
    				sum = 0;		
    			}
    		}
    	}
    }
    i made a void function so that i could use the printf, but i didnt get what i expected, any help would be appreciate, thanks
    Last edited by rob90; 11-29-2009 at 02:09 PM.

  2. #2
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    I thought an algorithm like this would work well:

    1) walk each row
    2) sum and average each two values
    3) any two that meet this criteria, keep scanning until all the contiguous values in the row that meet the criteria, have been found.

    4) at the starting column, then use the "flip" trick, to go down the column, continuing until all contiguous column values that meet the criteria, have been found.

    5) when you've done this for all the values found in #3, then add up the values in this submatrix. rows = stop row - start row, cols = stop col - start col. total = rows * cols.

    6) biggest total, wins.

    I'm a hobby coder, so there may be a much better way to do this.

    The "flip" trick is just putting the columns var in the inner nested loop
    Code:
    for(col = 0; col < someVariable; col++) {
      for(row = 0; row < someVariable; row++) {
          //just something to do in a column
         tally += grid[col][row];  //walk down a column in a 2D matrix.
      }
    }

  3. #3
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    Quote Originally Posted by Adak View Post
    I thought an algorithm like this would work well:

    1) walk each row
    2) sum and average each two values
    3) any two that meet this criteria, keep scanning until all the contiguous values in the row that meet the criteria, have been found.

    4) at the starting column, then use the "flip" trick, to go down the column, continuing until all contiguous column values that meet the criteria, have been found.

    5) when you've done this for all the values found in #3, then add up the values in this submatrix. rows = stop row - start row, cols = stop col - start col. total = rows * cols.

    6) biggest total, wins.

    I'm a hobby coder, so there may be a much better way to do this.

    The "flip" trick is just putting the columns var in the inner nested loop
    Code:
    for(col = 0; col < someVariable; col++) {
      for(row = 0; row < someVariable; row++) {
          //just something to do in a column
         tally += grid[col][row];  //walk down a column in a 2D matrix.
      }
    }
    allright.. but I still dont get it at the first second and third step, after scanning each row and having found the sum and average of each two values, do i have to keep those whose average is less than m? I dont get the "keep scanning until all the contiguous values in the row that meet the criteria have been found", sorry but im quite new to C, thanks for the help anyway

  4. #4
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by rob90 View Post
    allright.. but I still dont get it at the first second and third step, after scanning each row and having found the sum and average of each two values, do i have to keep those whose average is less than m? I dont get the "keep scanning until all the contiguous values in the row that meet the criteria have been found", sorry but im quite new to C, thanks for the help anyway
    I started a sample program, and quickly found the devil in the details. For example, say that none of the first row's averages came out less than m.

    fine, fine.

    Now you scan the 2nd row, and fine that the 4th, 5th, & 6th values, are less than m. And now you need to see whether, with these averages included, the 4th, 5th and 6th values from the *first* row, are now (after being averaged into the second rows average), also < m, and so should be included in the submatrix.

    IMO, that makes the algorithm unusable unless you're a glutton for punishment - and I'd avoid using it unless you see some insight to simplify it.

    OK, new algorithm. Simpler << yah! >>

    Simple and fast, but not completely accurate:
    You start with each value, and begin averaging the values in all 4 directions, with the adjacent index values.

    When the average > m, you stop, and check the submatrix for "squareness (no stairstepping), and write the indexes to maxIndex string, if it's the largest so far.

    While generally OK, this will fail when the data goes up over a "high spot" and then comes back down, later - because the high spot will stop your program from scanning further.

    The accurate, but far more computationally intensive way:

    for each element of the array, your program will generate every combination of row and column, index's, consistent with a square or rectangular array.

    From that, generate every average that is possible for any size submatrix.

    Largest one with an average < m, is the answer.

    so, first off, we need to id every possible square or rectangular submatrix, for every element of the array.

    00:
    across
    00 01
    00 01 02
    00 01 02 03

    down
    00 10
    00 10 20
    00 10 20 30
    00 10 20 30 40

    repeat for each element of the array.

    Taking that data, calculate the average for each one.

    Care must be taken to ensure that the submatrix is "squared off" so it's not stair-stepped, etc.

    This seems like a logic be damned sort of problem. If you try to do it the first one (which seems reasonable at first glance), then you'll soon be tied up in logic knots galore.

    Perhaps your instructor has mentioned some data structure or algorithm that is helpful for this.

    Since the matrix is not large, and the submatrix has to be squared (which knocks off a lot of combinations right there), the simpler and comprehensive way seems best to me.

    What do you think?

  5. #5
    Registered User
    Join Date
    Nov 2009
    Posts
    60
    Quote Originally Posted by Adak View Post
    Since ... the submatrix has to be squared
    Where do you read that? Sorry, I don't know about matrices, but can't a matrix be rectangular?

  6. #6
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Quote Originally Posted by hilarius View Post
    Where do you read that? Sorry, I don't know about matrices, but can't a matrix be rectangular?
    Yes, of course. It can't be "stair-stepped" or weird shaped though. Square or rectangular == "squared", in my shorthand.

  7. #7
    Registered User
    Join Date
    Nov 2009
    Location
    Italy
    Posts
    65
    I finally made it, took more than 3 hours of intense work lol, had to use a brute force algorithm solution, trying all the sums of the submatrices of S through 4 different iterations, one that checks all the submatrices starting from the top-right corner of the main matrix, one that starts from the top-left corner, one from bottom right and the last one from bottom left, everytime it goes either up or down obviously, thanks for the help Adak, cheers

  8. #8
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Congrats, Rob!

    I finally went out on the web, looking for something elegant. I know matrices have been studied to death, but for some reason I couldn't find anything (free).

    So I quit that and am just now coding up a brute force solution. It's anything *but* elegant, but it will do the job when it's done.

    Three hours is good time for coding up a brute force solution, imo.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. tools for finding memory leaks
    By stanlvw in forum C++ Programming
    Replies: 4
    Last Post: 04-03-2009, 11:41 AM
  2. Help needed! Finding Root of an Equation?
    By reader in forum C Programming
    Replies: 4
    Last Post: 06-13-2008, 10:10 AM
  3. Finding primes
    By starripper in forum C++ Programming
    Replies: 19
    Last Post: 01-14-2006, 03:17 PM
  4. Finding the smallest value......HARD!!!
    By AssistMe in forum C Programming
    Replies: 21
    Last Post: 03-10-2005, 05:23 AM
  5. MFC :: Finding Child Window of a CWnd* Object?
    By SyntaxBubble in forum Windows Programming
    Replies: 2
    Last Post: 09-06-2003, 09:06 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21