Comparing two arrays in C ignoring the order of the elements inside each array-CodePudding

I want to compare two arrays in C, ignoring the order of the elements inside each array, I had two ideas to solve this problem. Well, they're the same, to be honest. The first idea is to make a variable and increment it with 1 if we find our element inside the second table (please see the code below). But this one doesn't work if we give it as an example {3, 2, 2, 1} {1, 2, 3, 4}. the second idea (which I obviously couldn't code) is: setting a variable c=0 for example, after the first loop:

for (i = 0; i < n; i  ) {
    c = 0;
    for (...
}

this c will count the number of fails

if (T1[i] != T2[j]) {
    c  = 1
}

Then before exiting the j loop, we check if c==n where n is the length of the table. Meaning we have n fails. after that, unsetting cat the beginning of the i loop

this is my code:

#include <stdio.h>

int main() {
    int n, i, j, c = 0;
    printf("give the size of the first array: \n");
    scanf("%d", &n);
    int T1[n];
    int T2[n];
    // remplissage de T1
    for (i = 0; i < n; i  ) {
        printf("give the value of %d case, table1: ", i   1);
        scanf("%d", &T1[i]);
    }
    // remplissage de T2
    for (i = 0; i < n; i  ) {
        printf("give the value of %d case, table2: ", i   1);
        scanf("%d", &T2[i]);
    }
    for (i = 0; i < n; i  ) {
        for (j = 0; j < n; j  ) {
            if (T1[i] == T2[j]) {
                c  = 1;
                break;
            }
        }
    }
    if (c == n) {
        printf("True");
    } else {
        printf("False");
    }
}

CodePudding user response：

I think i've found what you are asking for. You need to do two double for to check equality in both ways, and then compare those 2 numbers.

    int c = 0;
    for(int i = 0; i < 4; i  ){
        for(int y = 0; y < 4; y  ){
            if(A1[i] == A2[y]){
                c  = 1;
                break;
            }
        }
    }
    
    int d = 0;
    for(int i = 0; i < 4; i  ){
        for(int y = 0; y < 4; y  ){
            if(A2[i] == A1[y]){
                d  = 1;
                break;
            }
        }
    }
    
    if(c != n || d != n || c != d){
        printf("False");
    }else{
        printf("true");
    }

If c and d are not the same it means that there is a duplicate that triggers 2 times the equal in one way. If c and d are the same but not equal to the array size it means that there are no duplicates, but not all the elements of one array are in the other.

I hope i've been helpfull

CodePudding user response：

With this approach

for (i = 0; i < n; i  ) {
    for (j = 0; j < n; j  ) {
        if (T1[i] == T2[j]) {
            c  = 1;
            break;
            }
        }
    }

the two arrays int T1[] = { 1, 1, 1, 1, 1 }; and int T2[] = { 1, 2, 3, 4, 5 }; will be always equal.

Also the approach with two pairs of such nested for loops where the arrays are swapped in the if statement will not help. In this case for example these arrays int T1[] = { 1, 2, 2, 2 }; and int T2[] = { 1, 1, 1, 2 }; again will be equal.

If you are allowed to sort arrays then you should sort the both arrays and compare them.

Otherwise you can use the approach shown in the demonstration program below.

#include <stdio.h>

int main( void )
{
    enum { n = 5 };

    int a1[n] = { 1, 2, 3, 2, 1 };
    int a2[n] = { 3, 2, 2, 1, 1 };

    int equal = 1;
    for (size_t i = 0; equal && i < n; i  )
    {
        size_t count = 1;
        for (size_t j = 0; j != i; j  )
        {
            if (a1[i] == a1[j])   count;
        }

        for (size_t j = 0; count && j < n; j  )
        {
            if (a2[j] == a1[i]) --count;
        }

        equal = count == 0;
    }

    printf( "The arrays are %sequal.\n", equal ? "" : "not " );
}

The program output is

The arrays are equal.

CodePudding user response：

Your approach fails if there are duplicates in the first array: { 0, 0 } will compare equal to { 0, 1 }. If you were to compare T1 and T2 both ways, you would still have this counter example: { 0, 0, 1 } and { 0, 1, 1 }.

You can work around this problem by counting the number of occurrences in both arrays of each element in one of the arrays: the arrays contain the same numbers if all counts match:

#include <stdio.h>

int count(int val, const int *T, int n) {
    int c = 0;
    for (int i = 0; i < n; i  )
        c  = (T[i] == val);
    return c;
}

int main() {
    int n, i;
    printf("give the size of the first array: \n");
    if (scanf("%d", &n) != 1)
        return 1;
    int T1[n];
    int T2[n];
    // remplissage de T1
    for (i = 0; i < n; i  ) {
        printf("give the value of %d case, table1: ", i   1);
        if (scanf("%d", &T1[i]) != 1)
            return 1;
    }
    // remplissage de T2
    for (i = 0; i < n; i  ) {
        printf("give the value of %d case, table2: ", i   1);
        if (scanf("%d", &T2[i]) != 1)
            return 1;
    }
    for (i = 0; i < n; i  ) {
        if (count(T1[i], T1, n) != count(T1[i], T2, n))
            break;
    }
    if (i == n) {
        printf("True\n");
    } else {
        printf("False\n");
    }
    return 0;
}

The above code has a time complexity of O(n²) because of the nested loops. You pay get better performance for large n by sorting both arrays and comparing them sequentially (complexity O(n.log(n)).)