how to find a sub matrix..

This is a discussion on how to find a sub matrix.. within the C Programming forums, part of the General Programming Boards category; I need to enter a number and find how many sub matrices exist which the sum of their members equals ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    how to find a sub matrix..

    I need to enter a number and find how many sub matrices exist which the sum of their
    members equals the input numbers.

    for this matrix
    8 6 0 3
    0 2 2 1
    0 2 2 4
    and number 8 it outputs 9
    i can find 9 sub matrices which the sum of their members equals the input number.

    http://img357.imageshack.us/img357/7137/38991334cz2.gif

    how to do this thing
    its like artificial intelligence
    Last edited by transgalactic2; 12-22-2008 at 02:46 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So, how did you find the nine submatrices which sum to the input number? Why can't your program do it the same way?

  3. #3
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i was given this example to act upon

    http://img357.imageshack.us/my.php?i...8991334cz2.gif

    those matrices could vary in size and shape
    there are too many possibilities

    ??
    Last edited by transgalactic2; 12-22-2008 at 12:28 PM.

  4. #4
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    So, do you think you could list all the submatrices of a given matrix? In a nice systematic way?

  5. #5
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i dont a have a systematic way

    ??

  6. #6
    Registered User C_ntua's Avatar
    Join Date
    Jun 2008
    Posts
    1,853
    For you given matrice

    8 6 0 3
    0 2 2 1
    0 2 2 4

    can you find the sub-matrices with an algorithm and not by hand?

    For example

    8 6 0
    0 2 2
    0 2 2

    8 6
    0 2
    0 2

    8
    0
    0

    8 6 0 3
    0 2 2 1

    8 6 0 3

    6 0 3
    2 2 1
    2 2 4

    6 0
    2 2
    2 2

    etc etc

  7. #7
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Is your smilie a member of the Order of the Arrow, or did that arrow commemorate an unfortunate archery incident?

  8. #8
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    cutting the matrix for each cell like it shows in the example
    and comparing the sum with an input number
    and printing the counter

    but its not working
    i get error like "ex2.exe encoutered an error"

    i marked the searching part by comments
    "start searching code"
    "end searching code"
    Code:
    #include <stdio.h>
    
    int main()   { //star
    	int i,j,k,temp,inp,sum2=0;
    	int rows = 50;
       int cols = 50;
       int jndex,input,counter=0;
    //	int sum2=0;  sum2 is never used
    
       /* You can't make an array without telling it's size. rows and cols
       have not been assigned a value, yet.
       */
       int matrix[50][50];
    //	int matrix[rows][cols];
    //	int sum[rows][cols];
       int sum[50][50];
    //	int temp1[rows][cols];
       int temp1[50][50];
    //	int transpose [cols][rows];
       int transpose [50][50];
    	int index,kndex,tndex,gndex,lndex;
       int rows_sum[50];
       //int rows_sum[rows]; //rows could be ANY value, still.
    
    /* your program isn't designed for this
       printf("enter rows and cols [1..50] ==> ");
    	scanf("%d %d",&rows,&cols);
    */
    
    /* You can save yourself this code, just by making the array initialize to
    zero's, when you declare it:
    row_sum[4] = { 0 };
    This only works when you first declare them, not at any later time
    */
     printf("enter the size of a  matrix:");
       scanf("%d %d",&rows,&cols);
    	for (index = 0; index < rows; index++)
    	{
    	    rows_sum[index]=0;
    		for (kndex = 0; kndex < cols; kndex++)
    		{
    			matrix[index][kndex] = 0;
    			sum[index][kndex] = 0;
    			temp1[index][kndex] = 0;
    			transpose[index][kndex] = 0;
    		}//end inner for
    	}//end outer for
    	printf("enter numbers in a row for a matrix:"); //stat input
    	for (index =0;index<rows; index++)
    	{
    		for (kndex =0; kndex<cols; kndex++)
    		{
    			scanf("%d", &matrix[index][kndex]);
    			transpose[kndex][index] = matrix[index][kndex];
    		}
    	}
    	i = getchar();  //needed because of scanf()
    	//end input
    printf(" enter number to search");
    scanf("%d", &inp);
                                                                                               //start of searching code
    for (tndex =rows;tndex>0; tndex++)
    	{
    		for (lndex =cols; lndex>0; lndex++)
    		{
    
                for (index =0;index<tndex; index++)
    	              {
    		                 for (kndex =0; kndex<lndex; kndex++)
    		                     {
    
    			                    sum2=sum2+matrix[index][kndex];
    		                      }
    	              }
    
              if (sum2==inp){
                counter++;
              }
    		}
    	}
    	                       
    	printf("%d",&counter);
    	                                                                                  // end of searching code
       return 0;
    
    }//end main
    Last edited by transgalactic2; 12-22-2008 at 03:17 PM.

  9. #9
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i reduce the top boundary
    and increase the lower boundary

    i marked the searching part by comments
    "start searching code"
    "end searching code"
    Code:
    #include <stdio.h>
    
    int main()   { //star
    	int i,j,k,temp,inp,sum2=0;
    	int rows = 50;
       int cols = 50;
       int jndex,input,counter=0;
    //	int sum2=0;  sum2 is never used
    
       /* You can't make an array without telling it's size. rows and cols
       have not been assigned a value, yet.
       */
       int matrix[50][50];
    //	int matrix[rows][cols];
    //	int sum[rows][cols];
       int sum[50][50];
    //	int temp1[rows][cols];
       int temp1[50][50];
    //	int transpose [cols][rows];
       int transpose [50][50];
    	int index,kndex,tndex,gndex,lndex;
       int rows_sum[50];
       //int rows_sum[rows]; //rows could be ANY value, still.
    
    /* your program isn't designed for this
       printf("enter rows and cols [1..50] ==> ");
    	scanf("%d %d",&rows,&cols);
    */
    
    /* You can save yourself this code, just by making the array initialize to
    zero's, when you declare it:
    
    row_sum[4] = { 0 };
    
    This only works when you first declare them, not at any later time
    */
     printf("enter the size of a  matrix:");
       scanf("%d %d",&rows,&cols);
    	for (index = 0; index < rows; index++)
    	{
    	    rows_sum[index]=0;
    		for (kndex = 0; kndex < cols; kndex++)
    		{
    			matrix[index][kndex] = 0;
    			sum[index][kndex] = 0;
    			temp1[index][kndex] = 0;
    			transpose[index][kndex] = 0;
    		}//end inner for
    	}//end outer for
    	printf("enter numbers in a row for a matrix:"); //stat input
    	for (index =0;index<rows; index++)
    	{
    		for (kndex =0; kndex<cols; kndex++)
    		{
    			scanf("%d", &matrix[index][kndex]);
    			transpose[kndex][index] = matrix[index][kndex];
    		}
    	}
    	i = getchar();  //needed because of scanf()
    	//end input
    printf(" enter number to search");
    scanf("%d", &inp);
    
                                     //start of searching code
            for (i =rows;i>0;i++)
                         {
                              for (j =cols;j>0;j++)
                                      {
                            for (tndex =rows;tndex>0; tndex++)
    	                         {
    		                            for (lndex =cols; lndex>0; lndex++)
    		                                   {
    
                                                      for (index=i;index<tndex; index++)
    	                                                     {
    		                                                   for (kndex =j; kndex<lndex; kndex++)
    		                                                            {
    
    			                    sum2=sum2+matrix[index][kndex];
    		                      }
    	              }
    
                                if (sum2==inp){
                                   counter++;
                                    }
    		                      }
    	                       }
                                      }
                         }
    
    	printf("%d",&counter);
    	                           // end of searching code
       return 0;
    
    }//end main

  10. #10
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    I built a code that does your algorithm using function i have build.
    I think there is problem in the array input on the signatures
    how input an array
    i tried int* matrix[][]

    ??
    Code:
    #include <stdio.h>
    
    int main()   { //star
    	int i,j,k,temp,sum3=0,total_sum=0,inp,sum2=0;
    	int rows = 50;
       int cols = 50;
       int jndex,input,counter=0;
       int matrix[50][50];
    //	int matrix[rows][cols];
    //	int sum[rows][cols];
       int sum[50][50];
    //	int temp1[rows][cols];
       int temp1[50][50];
    //	int transpose [cols][rows];
       int transpose [50][50];
    	int index,kndex,tndex,gndex,lndex;
       int rows_sum[50];
       
     printf("enter the size of a  matrix:");
       scanf("%d %d",&rows,&cols);
    	for (index = 0; index < rows; index++)
    	{
    	    rows_sum[index]=0;
    		for (kndex = 0; kndex < cols; kndex++)
    		{
    			matrix[index][kndex] = 0;
    			sum[index][kndex] = 0;
    			temp1[index][kndex] = 0;
    			transpose[index][kndex] = 0;
    		}//end inner for
    	}//end outer for
    	printf("enter numbers in a row for a matrix:"); //stat input
    	for (index =0;index<rows; index++)
    	{
    		for (kndex =0; kndex<cols; kndex++)
    		{
    			scanf("%d", &matrix[index][kndex]);
    			transpose[kndex][index] = matrix[index][kndex];
    		}
    	}
    	i = getchar();  //needed because of scanf()
    	//end input
    printf(" enter number to search");
    scanf("%d", &inp);
                                                              for (index=0;index<rows; index++)
    	                                                     {
    		                                                   for (kndex =0; kndex<cols; kndex++)
    		                                                            {
                                                                          sum3=search(inp ,i,j,rows,cols,matrix[][]);                               
                                                                  total_sum=total_sum+sum3;
    		                               }
    	                            }
    
    		                   //   }
    	                     //  }
                           //           }
                         //}
    
    	printf("%d",&counter);
    	                           // end of searching code
       return 0;
    }//end main
    
    int search(int input,int cor_row,int cor_col,int rows ,int cols,int* matrix[][]){//start search func
     int i,j,sum,counter=0;
     for ( i=rows;i>0;i--){
        for ( j=cols;j>0;j--){
      sum=sum_of_matrix(cor_row, cor_col,i ,j, matrix [][]);
      if (input==sum){
      counter++;
      }
    
        }
     }
     return counter;
    }//end search func
    
    
    int sum_of_matrix(int cor_row,int cor_col,int rows ,int cols,int* matrix [][]){
     int i ,j;
     int sum=0;
     for (i=cor_row;i<rows;i++){
         for (j=cor_col;i<cols;i++){
       sum=sum+matrix[i][j]
    
         }
     }
     return sum;
    }
    Last edited by transgalactic2; 12-22-2008 at 10:25 PM.

  11. #11
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i changed a code above
    i think it shuld work
    the problem is with tha array input in a function
    Last edited by transgalactic2; 12-22-2008 at 10:30 PM.

  12. #12
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    how to input an array in a function?

  13. #13
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    Your search for sub domains == 8 is very similar to how a queen searches a chessboard, for it's possible moves.

    Every matrix position will need to check in 8 directions: (using a clock for reference: 12, 1:30, 3, 4:30, 6, 7:30, 9, and 10:30 o'clock). That covers all rows, all columns, and all 4 diagonals, also.

    Edit: Nope, I see you're not using the diagonals - but you are using any 4 sided shape that adds up to 8 (in this case), and that the square is a part of (and hasn't been previously named).
    Last edited by Adak; 12-22-2008 at 11:14 PM.

  14. #14
    Registered User
    Join Date
    Sep 2006
    Posts
    8,868
    From a file, from the keyboard, or from an initial value?

  15. #15
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    i tried to implement this algorithm

    Quote Originally Posted by C_ntua View Post
    For you given matrice

    8 6 0 3
    0 2 2 1
    0 2 2 4

    can you find the sub-matrices with an algorithm and not by hand?

    For example

    8 6 0
    0 2 2
    0 2 2

    8 6
    0 2
    0 2

    8
    0
    0

    8 6 0 3
    0 2 2 1

    8 6 0 3

    6 0 3
    2 2 1
    2 2 4

    6 0
    2 2
    2 2

    etc etc
    i built the code above for it
    for each cell of the matrix i sent it to a function
    which
    for each row size it cuts a column

    and for that specific matrix i sent it to a function
    which calculates the sum of this matrix

    its a wrong algorithm?
    i cant check if its the right one
    because i cant input my array into the functions

    Code:
    #include <stdio.h>
    
    int main()   { //star
       int i,j,k,temp,sum3=0,total_sum=0,inp,sum2=0;
       int rows = 50;
       int cols = 50;
       int jndex,input,counter=0;
       int matrix[50][50];
    //   int matrix[rows][cols];
    //   int sum[rows][cols];
       int sum[50][50];
    //   int temp1[rows][cols];
       int temp1[50][50];
    //   int transpose [cols][rows];
       int transpose [50][50];
       int index,kndex,tndex,gndex,lndex;
       int rows_sum[50];
    
     printf("enter the size of a  matrix:");
       scanf("%d %d",&rows,&cols);
       for (index = 0; index < rows; index++)
       {
           rows_sum[index]=0;
          for (kndex = 0; kndex < cols; kndex++)
          {
             matrix[index][kndex] = 0;
             sum[index][kndex] = 0;
             temp1[index][kndex] = 0;
             transpose[index][kndex] = 0;
          }//end inner for
       }//end outer for
       printf("enter numbers in a row for a matrix:"); //stat input
       for (index =0;index<rows; index++)
       {
          for (kndex =0; kndex<cols; kndex++)
          {
             scanf("%d", &matrix[index][kndex]);
             transpose[kndex][index] = matrix[index][kndex];
          }
       }
       i = getchar();  //needed because of scanf()
       //end input
    printf(" enter number to search");
    scanf("%d", &inp);
    
    
                                                      for (index=0;index<rows; index++)
                                                            {
                                                             for (kndex =0; kndex<cols; kndex++)
                                                                      {
                                                                          sum3=search(inp ,i,j,rows,cols,matrix[][]);
                                                                  total_sum=total_sum+sum3;
                                         }
                                   }
    
       printf("%d",&counter);
     
       return 0;
    
    }//end main
    
    int search(int input,int cor_row,int cor_col,int rows ,int cols,int* matrix){//start search func
    
     int i,j,sum,counter=0;
    
    
     for ( i=rows;i>0;i--){
        for ( j=cols;j>0;j--){
      sum=sum_of_matrix(cor_row, cor_col,i ,j, matrix [][]);
      if (input==sum){
      counter++;
      }
        }
     }
     return counter;
    }//end search func
    
    
    int sum_of_matrix(int cor_row,int cor_col,int rows ,int cols,int* matrix [][]){
    
     int i ,j;
     int sum=0;
     for (i=cor_row;i<rows;i++){
         for (j=cor_col;i<cols;i++){
       sum=sum+matrix[i][j];
         }
     }
     return sum;
    }
    Last edited by transgalactic2; 12-23-2008 at 03:34 AM.

Page 1 of 3 123 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. getting orientation and position in opengl
    By ting in forum Game Programming
    Replies: 9
    Last Post: 07-07-2008, 04:13 PM
  2. Music Programming - Serial Matrix Display (Help needed)
    By CrazyHorse in forum C Programming
    Replies: 1
    Last Post: 11-13-2007, 03:28 PM
  3. Music Programming - Serial Matrix Display
    By CrazyHorse in forum C Programming
    Replies: 1
    Last Post: 11-12-2007, 03:16 PM
  4. working with rotation matrices
    By hannibar in forum Game Programming
    Replies: 23
    Last Post: 03-30-2005, 12:10 PM
  5. Matrix Reloaded Questions (SPOILERS_
    By Xei in forum A Brief History of Cprogramming.com
    Replies: 73
    Last Post: 10-19-2003, 02:21 PM

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