Finding the maximum row of a 4x4 matrix

Question

I have written a recursive function that I believe will return the 'maximum' row of the 4x4 matrix it is fed. By 'maximum' I mean that the maximum row of the matrix.

1 2 3 4
2 3 4 1
3 4 1 2
4 1 2 3

is row 4 (on account of the first column's values); the maximum row of the matrix

1 2 3 4
2 3 4 1
4 4 1 2
4 1 2 3

is row 3 (on account of the first and second columns' values); the maximum row of the matrix

1 2 3 4
2 3 4 1
4 4 1 2
4 4 2 3

is row 4 (on account of the first, second, and third columns' values); the maximum row of the matrix

1 2 3 4
2 3 4 1
4 4 1 2
4 4 1 3

is row 4 (on account of the values in every column); and the maximum row of the matrix

1 2 3 4
2 3 4 1
4 4 1 3
4 4 1 3

is row 3 (on account of the values in every column - pick the topmost row).

This function is a lot more involved than I expected when I sat down to write it. Please tell me there's an easier way to express this algorithm in C!

(The function is employed in a program written by a Pascalite; please forgive the fact that the arrays ignore their 0th member!)

Here's the function (together with its helper indexOf(), which is never fed an array in which val fails to appear!) Apologies for variable indentation - bit of a nightmare just getting it to this state!

int indexOf(int a[], int val) 
{ /* returns index at which val occurs in a[] */
    int i=1;

    while(a[i] != val)
        i++;

    return i;
}

int maxRow (int a[5][5], int index) 
{
  int store [5] = {-1, a[1][index], a[2][index], a[3][index], a[4][index] };
  int store2[5] = {-1, a[1][index], a[2][index], a[3][index], a[4][index] };

  int i, j, k, max, i1=0, i2=0, i3=0, i4=0;
  int arr[5]={-1,-1,store2[2],store2[3],store2[4]};

  if (index==5)
  {
    if(a[1][4]>=0)
        return 1;
    else if(a[2][4]>=0)
        return 2;
    else if(a[3][4]>=0)
        return 3;
    else if(a[4][4]>=0)
        return 4;               
  }

  /* order store[] from max -> min: */ 

  for(i=1; i<=3; i++)
  {  
    max=store[i]; 
    j=i;
    for(k=i+1; k<=4; k++)
        if(store[k]>max)
        {
            max=store[k];
            j=k;
        }
    store[j]=store[i]; 
    store[i]=max;
  } 

  i1 = indexOf(store2, store[1]);

  /* now we must indicate which (if any ) rows to recurse on... */

  if (store[1]==store[2])
  {         
    if(i1==1)           
        i2 = indexOf(arr,store[1]);     
    else if (i1==2)
    {
        arr[2] = -1;
        i2 = indexOf(arr, store[1]);        
    }
    else if (i1==3)
        i2 = 4;

    /* note: if i2==4 then can't have store[1] equal to any other members of store[] */

    if(store[1]==store[3])
    {
        /* i2 = 2 or 3 */

        if(store2[4] <= store2[3])          
            i3 = 3;         
        else i3=4;      

        if (store[1]==store[4])
        {
            i4=4;
        }
    }  
  }      

    if (i2==0) 
        return i1;

    else if(i3==0)
    {
          i = indexOf(store2,store[4]);

          for(j=0;j<5;j++)
            a[i][j]=-1; 

          i = indexOf(store2,store[3]);

          for(j=0;j<5;j++)
            a[i][j]=-1;         

          return maxRow(a, index+1);              
    }   
    else if (i4==0)
    {
      i = indexOf(store2,store[4]);

      for(j=0;j<5;j++)
            a[i][j]=-1; 
      return maxRow(a, index+1);
    }
    else /* all i are non-zero */
      return maxRow(a, index+1);
}

Answer 1

The first thing I'd do if I were refactoring this code is get rid of recursion.

You should be able to do it with a variable to keep track of "best row number so far", and a simple "for each row" loop. Inside the loop would be code that compares the current row with the best row so far (and does "best row so far = current row" if the current row is better).

Example:

int maxRow(int a[4][4]) {
    int i,j;
    int bestRow = 0;

    for(i = 1; i < 4; i++) {
        for(j = 0; j < 4; j++) {
            if(a[i][j] !=  a[bestRow][j]) {
                if(a[i][j] > a[bestRow][j]) {
                    bestRow = i;
                }
                break;
            }
        }
    }
    return bestRow;
}

Answer 2

One way to do this is to simply compare two rows at a time and find which rows are the greatest seen so far:

iterative version:

int maxrow(int *matrix, int width, int height) {       
    int maxrowindex = 0; // first, assume the first row is the maxrow
    int r, c;
    for (r = 0; r < height; r++) {
        for (c = 0; c < width; c++) {
            if (matrix[maxrowindex*width+c] != matrix[r*width+c]) {
                if (matrix[maxrowindex*width+c] < matrix[r*width+c]) {
                    maxrowindex = r;
                }
                break;
            }
        }
    }
    return maxrowindex;
}

recursive version:

int lexicographic_compare(int a[], int b[], int width) {
    if (width == 1) return a[0] <= b[0];
    if (a[0] == b[0]) return lexicographic_compare(a+1, b+1, width-1);
    return a[0] <= b[0];
}   
int maxrow(int *matrix, int width, int height) {
    if (height == 1) return 0;
    int a = 0;
    int b = maxrow(matrix + width, width, height-1) + 1;
    if (lexicographic_compare(matrix+a*width, matrix+b*width, width)) {
        return b;
    } else {
        return a;
    }   
}   

this code should work for a matrix of arbitrary size.

Answer 3

You could use strcmp(char*, char*) to compare two strings. If you convert the matrix rows to the equivalent characters, then the strcmp() will do the hard work for you.

int isFirstGreater = strcmp("1234", "1232");

This will return 1 to say that the first string is greater. In your context:

for(int i=0; i < MatrixSize; i++)
{
    charArray[i] = (char*) matrixRow[i];
}
charArray[MatrixSize] = 0; // You need to add a zero to make it a string. 
strcmp(charArray, anotherCharArray); 

However, this does seem like a bit of a crude hack.

Maybe this is better:

int number = 0;
for(int i=0; i< matrixSize; i++)
{
    number += matrixRow[i] * pow(10, (matrixSize-i)-1);
}

That just converts the matrix row to a number, which you can just use >, < to see which is bigger, which is the equivalent to your original goal.

Answer 4

A non-recursive solution could look like this (sorry, no C code, but an algorithm description instead):

• Keep a bool array row_ruled_out[4] with one item per row. This array will be used to keep track of which rows have already been "ruled out". Initially, all rows are still considered "in".

• For each column of your matrix, do the following:

  1. Find the maximum number m appearing in the column. For example, in the following matrix column:

       . a . .
       . b . .
       . c . .
       . d . .
     

     m = max(a, b, c, d).

  2. For each row that hasn't yet been ruled out (according to row_ruled_out), if its value in that column is less than m, it cannot be the largest row. Therefore mark that row as "ruled out" in the row_ruled_out array. It won't be considered any further.

• After you've done the above for each column, look at row_ruled_out. All rows that are left, ie. haven't been ruled out, must be the largest rows. This could be zero, one, or several rows, depending on your input.

Answer 5

with tests.... just comparing every row....

#include "seatest.h"


int m1[4][4] = { 
    {1,2,3,4},
    {2,3,4,1},
    {3,4,1,2},
    {4,1,2,3}};


int m2[4][4] = { 
    {1,2,3,4},
    {2,3,4,1},
    {4,4,1,2},
    {4,1,2,3}};

int m3[4][4] = { 
    {1,2,3,4},
    {2,3,4,1},
    {4,4,1,2},
    {4,4,2,3}};

int m4[4][4] = { 
    {1,2,3,4},
    {2,3,4,1},
    {4,4,1,2},
    {4,1,1,3}};

int m5[4][4] = { 
    {1,2,3,4},
    {2,3,4,1},
    {4,4,1,3},
    {4,1,1,3}};


int compare(int* d1, int* d2, int l)
{
    int i;
    for(i=0; i<l; i++) 
    {
        if(d1[i] > d2[i]) return 1;
        if(d1[i] < d2[i]) return -1;
    }
    return 0;
}

int matrix_max_row_r(int* m, int w, int h)
{
    int i;  
    int max = 0;
    for(i=1; i<h; i++) max = compare(m+(w*i), m+(w*(i-1)), w) > 0 ? i : max;
    return max;
}



int matrix_max_row(int* m)
{
    return matrix_max_row_r(m, 4,4);
}


void test_max_matrix_row()
{   
    assert_int_equal(3, matrix_max_row((int*)m1));
    assert_int_equal(2, matrix_max_row((int*)m2));
    assert_int_equal(3, matrix_max_row((int*)m3));
    assert_int_equal(2, matrix_max_row((int*)m4));
    assert_int_equal(2, matrix_max_row((int*)m5));
}

void test_fixture_matrix( void )
{
    test_fixture_start();      
    run_test(test_max_matrix_row);   
    test_fixture_end();       
}

void all_tests( void )
{
    test_fixture_matrix();   
}

int main( int argc, char** argv )
{
    run_tests(all_tests);   
    return 0;
}