0

What aprroach should I be using to write a function which checks if a matrix is contained in another matrix? For example:

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

I added the dots to point out the matrix B inside matrix A.

I've written this so far:

#include <stdio.h>

int matrica_sadrzana(int* m1, int v1, int s1, int* m2, int v2, int s2){

    /* What needs to go here? */
    return 0;
}

int main() {
    int i,j,v1,v2,s1,s2,sadrzana;
    int matricaA[100][100],matricaB[100][100];
    printf("Unesite visinu i sirinu matrice A: ");
    scanf("%d %d",&v1,&s1);
    printf("Unesite visinu i sirinu matrice B: ");
    scanf("%d %d",&v2,&s2);
    for(i=0; i<v1; i++){
        for(j=0; j<s1; j++){
            scanf("%d",&matricaA[i][j]);

        }
    }
    for(i=0; i<v2; i++){
        for(j=0; j<s2; j++){
            scanf("%d",&matricaB[i][j]);

        }
    }
    sadrzana=matrica_sadrzana(matricaA,v1,s1,matricaB,v2,s2);

    return 0;
}
Raydel Miranda
  • 13,825
  • 3
  • 38
  • 60
syd
  • 13
  • 4
  • Should changes parameters from `int* m1` to `int s1, int m1[][s1]`. You can specify the second dimension that way. – Austin Stephens Dec 13 '18 at 00:49
  • I believe your question is how do you find whether an element/integer from one array/matrix is contained within another array/matrix? – Austin Stephens Dec 13 '18 at 00:53
  • Oh, that makes sense. But what with the logic for checking the elements of the matrix, that's what's really troubling me. Can you give me some hints on that? – syd Dec 13 '18 at 00:57
  • Yes that's what I'm asking. Not only one, but the whole matrix B. A way to determine if elements of matrix B are contained in matrix A in such order that doesn't change the order of matrix B. – syd Dec 13 '18 at 00:58
  • [This answer](https://stackoverflow.com/a/47235897/841108) could be inspirational – Basile Starynkevitch Dec 13 '18 at 06:09
  • Your compiler should be complaining about two type mismatches between the matrices passed to the function and what the function expects. You are not using variable length arrays (VLA), so the size (specifically, the second dimension, 100) needs to be specified on both arrays, so that you access the correct data. For example, `int matrica_sadrzana(int m1[][100], int v1, int s1, int m2[][100], int v2, int s2){` — might allow you to write appropriate code inside the function with the current function call. – Jonathan Leffler Dec 13 '18 at 06:42

2 Answers2

0

You can create a findNum() function that returns a boolean value of true or false, and takes in a row size, col size, 2d array (with the 2nd dimension specified by the col size being passed in) and a number you would like to check for. So in your case, you could traverse through Matrix A calling findNum() for every element in Matrix A to check and see if Matrix B contains it. findNum() will return true at the first encounter of the number it's checking for. If the number is not in there then it will return false.

For example:

_Bool findNum(int row, int col, int arr2d[][col], int chk) {
    for(int i = 0; i < row; ++i) {
        for(int j = 0; j < col; ++j) {
            if(arr2d[i][j] == chk)
                return 1;
        }
    }

    return 0;
}

Using it (this should print "Match!" three times since 0 is contained in arr2d2 but 5 is not):

int arr2d1[2][2] = {0};
int arr2d2[2][3] = {0};

/* Change a value in arr2d1 so they're not identical */
arr2d1[0][0] = 5;

/* Element we're sending to findNum() */
int element = 0;

/* Traverse through arr2d1 */
for(int i = 0; i < 2; ++i) {
    for(int j = 0; j < 2; ++j) {
        element = arr2d1[i][j];
        /* Check if the current element is contained
         * in arr2d2; do whatever if so */
        if(findNum(2, 3, arr2d2, element)) {
            printf("Match!\n");
        }
    }
}
Austin Stephens
  • 401
  • 4
  • 9
0

You can do this using fixed length arrays or variable length arrays.

Fixed length arrays

You started with fixed length arrays, so the first program follows your lead. You have to specify the second dimension of the arrays when you pass them — otherwise, the code will be accessing the wrong data. Your compiler should have been complaining about the call to your function. I used initialized data rather than reading from standard input. The input code is commented out (and untested).

#include <stdio.h>

static int matrica_subset(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
    for (int m = 0; m < r2; m++)
    {
        for (int n = 0; n < c2; n++)
        {
            printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r1+m, c1+n, m1[r1+m][c1+n], m, n, m2[m][n]);
            if (m1[r1+m][c1+n] != m2[m][n])
                return 0;
        }
    }
    return 1;
}

static int matrica_sadrzana(int m1[][100], int r1, int c1, int m2[][100], int r2, int c2)
{
    if (c1 < c2 || r1 < r2)
        return 0;
    int c_max = c1 - c2 + 1;
    int r_max = r1 - r2 + 1;
    for (int r = 0; r < r_max; r++)
    {
        for (int c = 0; c < c_max; c++)
        {
            printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
            if (m1[r][c] == m2[0][0])
            {
                if (matrica_subset(m1, r, c, m2, r2, c2) != 0)
                {
                    printf("match at m1[%d][%d]\n", r, c);
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(void)
{
    int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
    int matricaA[100][100] =
    {
        {   1,   2,   3,   4,   5, },
        {   6,   7,   8,   9,  10, },
        {  11,  12,  13,  14,  15, },
        {  16,  17,  18,  19,  20, },
    };
    int matricaB[100][100] =
    {
        {   2,   3, },
        {   7,   8, },
        {  12,  13, },
    };

    //printf("rows and columns for matrix A: ");
    //scanf("%d %d", &r1, &c1);
    //printf("rows and columns for matrix B: ");
    //scanf("%d %d", &r2, &c2);
    //printf("data for matrix A:\n");
    //for (int i = 0; i < r1; i++)
    //{
    //    for (int j = 0; j < c1; j++)
    //    {
    //        scanf("%d", &matricaA[i][j]);
    //    }
    //}
    //printf("data for matrix B:\n");
    //for (int i = 0; i < r2; i++)
    //{
    //    for (int j = 0; j < c2; j++)
    //    {
    //        scanf("%d", &matricaB[i][j]);
    //    }
    //}

    sadrzana = matrica_sadrzana(matricaA, r1, c1, matricaB, r2, c2);
    printf("sadrzana: %d\n", sadrzana);

    return 0;
}

The matrica_subset() function looks in m1 starting at row r1, column c1 for a match with m2 with size r2 active rows and c2 active columns (a tiny subset of the 100x100 matrix defined in main()).

The matrica_sadrzana() coordinates the search, checking whether the top-left corner of m2 matches the current position in m1 and continuing the search with the matrica_subset() function when there is a match.

Sample output:

sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 19; m2[2][1] = 13
sa: m1[0][2] = 3; m2[0][0] = 2
sa: m1[0][3] = 4; m2[0][0] = 2
sa: m1[1][0] = 6; m2[0][0] = 2
sa: m1[1][1] = 7; m2[0][0] = 2
sa: m1[1][2] = 8; m2[0][0] = 2
sa: m1[1][3] = 9; m2[0][0] = 2
sadrzana: 0

Variable length arrays

The alternative using variable length arrays needs extra parameters to the matrica_subset() function to specify the actual size of the array (r1 and c1) and also the search position in the array (r0 and c0).

#include <stdio.h>

static void dump_matrix(const char *tag, int r, int c, int m[r][c])
{
    printf("%s (%dx%d):\n", tag, r, c);
    for (int i = 0; i < r; i++)
    {
        for (int j = 0; j < c; j++)
            printf(" %3d", m[i][j]);
        putchar('\n');
    }
}

static int matrica_subset(int r1, int c1, int m1[r1][c1], int r0, int c0, int r2, int c2, int m2[r2][c2])
{
    for (int m = 0; m < r2; m++)
    {
        for (int n = 0; n < c2; n++)
        {
            printf("ss: m1[%d][%d] = %d; m2[%d][%d] = %d\n", r0+m, c0+n, m1[r0+m][c0+n], m, n, m2[m][n]);
            if (m1[r0+m][c0+n] != m2[m][n])
                return 0;
        }
    }
    return 1;
}

static int matrica_sadrzana(int r1, int c1, int m1[r1][c1], int r2, int c2, int m2[r2][c2])
{
    if (c1 < c2 || r1 < r2)
        return 0;
    int c_max = c1 - c2 + 1;
    int r_max = r1 - r2 + 1;
    for (int r = 0; r < r_max; r++)
    {
        for (int c = 0; c < c_max; c++)
        {
            printf("sa: m1[%d][%d] = %d; m2[0][0] = %d\n", r, c, m1[r][c], m2[0][0]);
            if (m1[r][c] == m2[0][0])
            {
                if (matrica_subset(r1, c1, m1, r, c, r2, c2, m2) != 0)
                {
                    printf("match at m1[%d][%d]\n", r, c);
                    return 1;
                }
            }
        }
    }
    return 0;
}

int main(void)
{
    int sadrzana, c1 = 5, c2 = 2, r1 = 4, r2 = 3;
    int matricaA[4][5] =
    {
        {   1,   2,   3,   4,   5, },
        {   6,   7,   8,   9,  10, },
        {  11,  12,  13,  14,  15, },
        {  16,  17,  18,  19,  20, },
    };
    int matricaB[3][2] =
    {
        {   2,   3, },
        {   7,   8, },
        {  12,  13, },
    };

    //printf("rows and columns for matrix A: ");
    //scanf("%d %d", &r1, &c1);
    //printf("rows and columns for matrix B: ");
    //scanf("%d %d", &r2, &c2);
    //printf("data for matrix A:\n");
    //for (int i = 0; i < r1; i++)
    //{
    //    for (int j = 0; j < c1; j++)
    //    {
    //        scanf("%d", &matricaA[i][j]);
    //    }
    //}
    //printf("data for matrix B:\n");
    //for (int i = 0; i < r2; i++)
    //{
    //    for (int j = 0; j < c2; j++)
    //    {
    //        scanf("%d", &matricaB[i][j]);
    //    }
    //}
    dump_matrix("Matrix A", r1, c1, matricaA);
    dump_matrix("Matrix B", r2, c2, matricaB);

    sadrzana = matrica_sadrzana(r1, c1, matricaA, r2, c2, matricaB);
    printf("sadrzana: %d\n", sadrzana);

    return 0;
}

Sample output:

Matrix A (4x5):
   1   2   3   4   5
   6   7   8   9  10
  11  12  13  14  15
  16  17  18  19  20
Matrix B (3x2):
   2   3
   7   8
  12  13
sa: m1[0][0] = 1; m2[0][0] = 2
sa: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][1] = 2; m2[0][0] = 2
ss: m1[0][2] = 3; m2[0][1] = 3
ss: m1[1][1] = 7; m2[1][0] = 7
ss: m1[1][2] = 8; m2[1][1] = 8
ss: m1[2][1] = 12; m2[2][0] = 12
ss: m1[2][2] = 13; m2[2][1] = 13
match at m1[0][1]
sadrzana: 1

Surprise, surprise — it returns the same result. The searching functions work with variable length arrays; the data is still stored in fixed size arrays (because you can't use an initializer for a VLA), but the sizes are dramatically smaller than in the original code.

The VLA code also dumps the input matrices; the FLA code does not. It's fairly easy to add the dumping code to the first program, but the print function isn't as generic. It would be possible to arrange to dump an NxM subsegment of an RxC matrix; that's marginally fiddly to code, but very generic and could be used in both programs — but the VLA program would simply set N and R equal, and M and C equal.

Jonathan Leffler
  • 730,956
  • 141
  • 904
  • 1,278
  • Hey, thank you very much! But I managed to solve it on my own, it's similiar to your "fixed lenght array" solution, but mine is with one function and four nested loops, I can send you if you're interested. Thanks for the answer! – syd Dec 13 '18 at 19:24
  • I had a version with 4 loops, and a goto to break out of the innermost loop. That was when I wrote the subset function. It has the two inner loops and uses return instead of goto. Since it is static and called just once, a decent compiler will inline it anyway – Jonathan Leffler Dec 13 '18 at 23:11