# Thread: how to find a sub matrix..

1. ## 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

2. 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. 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

??

4. So, do you think you could list all the submatrices of a given matrix? In a nice systematic way?

5. i dont a have a systematic way

??

6. 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. Is your smilie a member of the Order of the Arrow, or did that arrow commemorate an unfortunate archery incident?

8. 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```

9. 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. 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;
}```

11. i changed a code above
i think it shuld work
the problem is with tha array input in a function

12. how to input an array in a function?

13. 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).

14. From a file, from the keyboard, or from an initial value?

15. i tried to implement this algorithm

Originally Posted by C_ntua
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;
}```