Which is the fastest way to return the number of different rows in a matrix A?

Question

If i have the following matrix A:

A = {1,2,3}
    {7,9,1}
    {5,3,2}

how i can easily return the number of different rows in the Matrix? In this case the output must be : "3"

i tried to make a function "rows":

void rows (int a[N][N], int row[N], int x){

    for (int i=0;i<N;i++){

        row[i]=a[x][i];


    }

}

then, with the function "check" i tried to check if the rows are different:

int check ( int a[N][N])
{

    int row1[N];
    int row2[N];

    int j=0;

    rows(a,row1,j);
    rows(a,row2,j+1); 


    int count = 0;


    for ( int i=0; i<N; i++){
        for ( int j=0; j<N; j++){


            if ( row1[i] != row2[j]){

                count++;

            }

        }
    }


    return count;

}

but return the wrong number , any suggestions ?

Answer 1

Your algorithm is entirely wrong. With an added break it "works" when all rows are different, but it breaks when some of the rows are the same. It counts the number of rows such that there exists another row that's different from it. For example, if you run it on

1 2 3
4 5 6
1 2 3

you will get an answer 3, but you should get a 2.

The algorithm should go like this:

• Assume that all rows are distinct (result = N)
• For each row i, look at the rows below it
• If any of the rows j below the row i is equal to row[i], decrement the result and break out of the inner loop
• At the end of the outer loop, result contains your answer.

Answer 2

Implement a 'CompareRows' functor as a predicate for set. Then, all you need to do is --

typedef vector<int> Rows;
set<Rows, CompareRows> UniqRows;

for ( int i = 0 ; i < N ; ++i )
  UniqRows.insert(Rows(a[i], a[i] + N));

UniqRows.size();