0

Let's say we have two matrices A and B with the same dimensions. Is there any way to check if B is a permutation of A without any special functions or libraries in C ?

     #include <stdio.h>
     int intersection(int r[20][20],int f,int g,int m){
     int i,j;
     for (i=0;i<f;i++){
         for (j=0;j<g;j++){
            if (r[i][j]==m)
             return 1;
             }
           }
             return 0;
 }
    int main() {
    int m[20][20],m1[20][20],a,b,i,j,l,k,counter=0;
    scanf("%d %d", &a, &b);
    for (i=0;i<a;i++){
        for (j=0;j<b;j++){
        scanf("%d",&m[i][j]);
       }
      }

     for (i=0;i<a;i++){
         for (j=0;j<b;j++){
          scanf("%d",&m1[i][j]);
         }
      }
       for (i=0;i<a;i++){
           for (j=0;j<b;j++){
        if (intersection(m1,a,b,m[i][j])==1)
        counter++;
          }
      }
      if (counter==a*b)
         printf("YES");
   }
Michael
  • 33
  • 5
  • No. Either you'll have to find a library that does it, or you'll have to write code to do it. What constitutes a permutation? Just the same (multi)set of numbers in any order? Or do either the rows or the columns have to be the same? Why the prohibition on sorting? If you're dealing with the 'same (multi)set of numbers', then sorting is likely to be quickest way — generate a sorted vector of numbers (and counts) for each array, and check that those vectors are the same. – Jonathan Leffler Dec 26 '20 at 17:32
  • @Jonathan Leffler Yes, I know how to solve this with libraries, so I'm interested if anyone knows how to solve this without them. – Michael Dec 26 '20 at 17:37
  • You write code equivalent to the code in the libraries. There is nothing built into C or the Standard C library (or the POSIX library, come to that) that will help — it works at a lower level than matrix operations. – Jonathan Leffler Dec 26 '20 at 17:38
  • You could do it without sorting if the range of values is small: just tally up the usage of each value, in an array. – Weather Vane Dec 26 '20 at 17:56
  • @JonathanLeffler I deleted the restriction on sorting, just without functions and libraries – Michael Dec 26 '20 at 18:00
  • 1
    Without sorting: Create a Boolean array `used` with the same dimensions, initialized to `false` in each element. For each element in A, search an element in B that is equal and for which the corresponding `used` entry is false. If not found, B is not a permutation of A. If found, mark the corresponding `used` entry true and go on to the next element of A. If all elements of A are found, B is a permutation of A. With sorting: Sort A. Sort B. B was a permutation of A if and only if the sorted A equals the sorted B. – Eric Postpischil Dec 26 '20 at 18:03
  • Without sorting or non-constant extra space: Count how many times the first element in A appears in A and how many times it appears in B. If different, B is not a permutation of A. If same, go on to the next element in A that does not equal the first. Count in A and B and compare. Also change every found matching element to the value of the first element in A. Repeat until the end of A is reached. – Eric Postpischil Dec 26 '20 at 18:06
  • @EricPostpischil I tried to write the code, but something doesn't work in it. Is there any way to correct it? – Michael Dec 27 '20 at 00:29

0 Answers0