Matrix sorting

Along time ago someone posted this question. Has any one found a linear algorithm that "sorts" a matrix like this.

Code:

0100
0010
1011
1010

into

Code:

1010
0100
0010
1011

 

Log in or Sign up to hide all adverts.

Actually I think the other question wasn't to do a conversion from one matrix to another, but to actually write one disorganised 'matrix' into an organised one. The organisation being that it went from lower values in the top line to higher ones in the bottom line.

Simplest algorythm I can think of would be (M1+M2)-M1=M2
Where M1 is the first matrix and M2 is the second Matrix, of course my sum is written a little wrongly since there is a transposition of the first occurances of M2 to the actual answer of M2 but it's the simplest if you were after an equation.

However you will also note that if the matrix was suppose to only be 1's and 0's then that equation is too simplified to work since you might end up with 2's.

So when you get to a "2" you'd have to alter the Binary data in the area to deal with the change (from 011 to 100 etc)

 

Log in or Sign up to hide all adverts.

I think it can be solved by doing this
Take

Code:

0011
0100
1001
1010

The rows are then
0011 0100 1001 1010

The columns are
0011 0100 1001 1010

In order to find the first column and first row we have something like
1xxx
xxxx
xxxx
xxxx

Where the 'x's are don't cares. It should be evident that to have '1' at the top left there must be a row that looks like 1xxx and a column that looks like 1xxx. If we pick the first two that we come across by sequentially looking at the 2*n possibilities, then we know the sorted matrix looks like
1001
0xxx
0xxx
1xxx

Then the matrix formed by the don't cares has rows: 011, 100, 010 and columns: 011, 100, 010. And we should be able to apply the same procedure. The resultant algorithm in the worst case will examine each square, so time O(n^2) or linear if n is just the number of entries.

I'm a bit uncertain if it works in all cases, though.

 

Log in or Sign up to hide all adverts.

The other thing I neglected to mention was the potential of an Identity matrix.

1xxx
x1xx
xx1x
xxx1

You'll notice the ones align in the Matrix you want it to be, and don't align in the starting matrix. It could be possible for the program to test until that array is met, however you will notice that some of the inputs share some bytes, so obviously it would have to be tested to conclude if the full matrix had been assigned or if it fails during placement.

 

I think there are algorithms for triangular decomposition(not exactly a diagonal with all ones). I think the algorithm would be more complicated than linear though. The normal way to multiply two matrixs is O(n^3), though slightly faster algorithms exist.

Although there are special cases where the algorithm I described will not work, they be readily fixed.

For example, if you had the matrix

Code:

0110
1000
1100
1101

You could scan the first row of the first column to look for one, and then swap the column found with the first column. Since the first one is (1, 1), the resulting matrix would look like the following.

Code:

1  011
  ****
0*100
1*101
1*101

The inner matrix that is formed is similar to the larger matrix, and while swapping the columns and rows of the inner matrix will change the border around the matrix, no swap will of the inner matrix's columns or rows can modify the top left digit.

Because the top left of the inner matrix is already one, no change is necessary. We then go to solving this problem

Code:

10 11
01 00
    **
11*01
11*01

We scan for the first one and find row 1, column 2 of the inner matrix. We may then swap this column with column 1

Code:

10 11
01 00
    **
11*10
11*10

Decomposing the problem we have

Code:

101 1
010 0
111 0
    **
111*0

Since the inner matrix is 0, insead of look at the board around the inner matrix, we must either swap row 4 with a column that not only preserves the diagonal of ones built so far but will change the inner matrix of 0 to 1. This can be done, I think, in O(n) time, and so we swap the first row with the last row. The resulting matrix is

Code:

1110
0100
1110
1011

Of course, you could also have a matrix like

Code:

11 11
11 11
    **
11*00
11*00

But a similar O(n) search should find that we can swap the first row with the third row.

 

i posted the problem

Please Register or Log in to view the hidden image!

and it didn't have to be linear.. just polynomial complexity...

i've looked at the method you used and i am not convinced that it guarantees polynomial time, just because your algorithm finds itself in necessity of swapping with the first row, which in worst case could result in attempting all n! combinations of rows (where n is the number of rows). i think i came up with the algorithm that sorts a square matrix in polynomial time. i have to relook at and run some computer tests to show its validity, if it works i'll share it with y'all

Please Register or Log in to view the hidden image!

 

btw.. here is the original thread

http://www.sciforums.com/showthread.php?t=36110

 

Ok, I'll also write some C code to test this out.

 

This is the same greedy approach as was put forth in the original thread. It's not guaranteed to suceed, and not just in a small number of cases. Though I don't have any concrete numbers, I'd wager the cases take up a fairly significant amount of the search space. A way to characterize these cases is as follows:

1) Two rows (r1 and r2) have a 1 in a column X
2) r1 has a 1 in column Y
3) No other rows have a 1 in column Y

So as you can see, r1 needs to go in position Y, since it's the only one with a 1 there. However, if r1 is seen before r2 and put into position X, the algorithm fails. Naturally these cases can be arbitrarily complex--they don't need to involve only two rows.

The above aside, I have a few questions about your algorithm.

You make the following assumption about the upper left digit:

But later in the algorithm, you swap the first row with the fourth row. Luckily, the fourth row had a 1 in the first position. But what if this wasn't the case?

The following step also confuses me:

Here you actually swap two columns, not rows. The problem as stated in the original thread only allows for row swaps, not column swaps.

Example of an input on which your algorithm would fail:

Code:

10001
00110
10000
01100
01010

 

The problem I'm having is not that the algorithm is too slow but fixing the problems when there's 0 diagonals.

For example, this code here will create a matrix with 1's on the diagonals. But the last locations of the diagonal will not be filled in.

Code:

#include <stdio.h>

#define M 4
#define N 4

void sort_matrix_recur(int A[M][N], int row, int col);
void sort_matrix(int A[M][N]);

void swap_col(int A[M][N], int c1, int c2)
{
    int i;
    int t;

    for (i = 0; i < M; ++i) {
        t = A[i][c1];
        A[i][c1] = A[i][c2];
        A[i][c2] = t;
    }
}

void swap_row(int A[M][N], int r1, int r2)
{
    int i;
    int t;

    for (i = 0; i < N; ++i) {
        t = A[r1][i];
        A[r1][i] = A[r2][i];
        A[r2][i] = t;
    }
}

void print_matrix(int A[M][N])
{
    int i, j;

    for (i = 0; i < M; ++i) {
        for (j = 0; j < N; ++j) {
            printf("%d ", A[i][j]);
        }
        putchar('\n');
    }

    putchar('\n');
}


/* not working yet. Problems also in the explanation given before  */
void replace_zero_diag(int A[M][N])
{
   
}



/* sort a matrix recursively. */
void sort_matrix_recur(int A[M][N], int row, int col)
{
    int col_with_one = -1;
    int row_with_one = -1;
    int i;

    if (row >= M || col >= N) {
        replace_zero_diag(A);
        return;
    }

    if (A[row][col] != 1) {
        /* search outer topmost row for 1 digit */
        for (i = col; i < N && col_with_one == -1; ++i) {
            if (A[row][i] == 1)
                col_with_one = i;
        }

        if (col_with_one == -1) {
            // search outer leftmost column for 1 digit */
            for (i = row; i < M && row_with_one == -1; ++i) {
                if (A[i][col] == 1)
                    row_with_one = i;
            }
        }   

     
        if (col_with_one != -1) {
            printf("swap column %d with %d\n", col, col_with_one);
            swap_col(A, col, col_with_one);
        } else if (row_with_one != -1) {
            printf("swap row %d with %d\n", row, row_with_one);
            swap_row(A, row, row_with_one);
        } else {    

        }

    }

    sort_matrix_recur(A, row + 1, col + 1);
}


void sort_matrix(int A[M][N])
{
    sort_matrix_recur(A, 0, 0);
}


int main(void)
{
    /* matrix that will fail */
    int A[M][N] = {{1, 0, 1, 0},
                        {0, 1, 0, 1},
                        {0, 1, 0, 0},
                        {1, 0, 0, 0}};

    sort_matrix(A);
    print_matrix(A);

    return 0;
}

So this code will get the matrix into form where the diagonal consists of a series of 1's followed by '0', and does so in polynomial time. But the last procedure of replace_zero_digit must be done.

 

There's no column swap in the original problem. Allowing that results in a completely new problem definition and solution.

 

Thanks, I think the problem might be easier without the column swaps. Instead of working with row swaps, I'll just work column swaps on a transposed matrix as its easier to visualize. I think it's possible to use an algorithm similar to above to produce all 1s on one part of the diagonal and don't cares on the rest. Once that point is reached another algorithm must be developed. For instance

Code:

10001 
00110
10000
01100
01010

may be reduced to

Code:

10 001
01 010 
    ___     
10|000
01|100
00|110

Because there is no column within the small matrix that may be swapped, in order to fill a one at the upper-left corner of the small matrix, a column left of the smaller matrix with 1 at the appropriate position must be swapped. In order to preserve the one diagonal already formed, that column must be swapped by a column within the smaller matrix that has a 1 as its top corner. To find both such columns and to swap them should require polynomial time.

 

It sounds simple enough for this example, but I bet there's a non-trivial input that will muck things up. I'll see if I can come up with one on Monday.

 

OK, here's some sourcecode of the algorithm that I think is correct. Also for some matrices it's impossible to sort the matrix.

Code:

#include <stdio.h>       /* stdio.h */
#include <stdlib.h>      /* stdlib.h */
#include <assert.h>     /* assert.h */

#define M 5
#define N 5

void sort_matrix_recur(int A[M][N], int row, int col);
void sort_matrix(int A[M][N]);
void print_matrix(int A[M][N]);
void replace_zero_digit(int A[M][N], int first_row, int first_col, int row, int col);
void replace_zero_diag(int A[M][N]);
int valid_matrix(int A[M][N]);

void swap_col(int A[M][N], int c1, int c2)
{
    printf("swapping columns %d, %d\n", c1, c2);
    int i;
    int t;

    for (i = 0; i < M; ++i) {
        t = A[i][c1];
        A[i][c1] = A[i][c2];
        A[i][c2] = t;
    }

    print_matrix(A);
}



void print_matrix(int A[M][N])
{
    int i, j;

    for (i = 0; i < M; ++i) {
        for (j = 0; j < N; ++j) {
            printf("%d ", A[i][j]);
        }
        putchar('\n');
    }

    putchar('\n');
}

void replace_zero_digit(int A[M][N], int first_row, int first_col, int row, int col)
{
    int i, j;

    int left = -1;
    int right = -1;

    for (i = 0; i < first_col && left == -1; ++i) {
        if (A[row][i] == 1) {
            for (j = first_col; j < N && left == -1; ++j) {
                if (A[i][j] == 1) {
                    left = i;
                    right = j;
                }
            }
        }
    }

    if (left != -1 && right != -1) {
        assert(A[left][left] == 1);
        assert(A[left][right] == 1);

        swap_col(A, left, right);

        print_matrix(A);
        swap_col(A, right, col);
        assert(A[first_row][first_col] == 1);
    }
}

void replace_zero_diag(int A[M][N])
{
    int row = 0;
    int col = 0;
    int first_row;
    int first_col;

    while(A[row][col] == 1) {       
        row++;
        col++;
    }

    if (row >= M || col >= N)
        return;

    first_row = row;
    first_col = col;
    
    while(row < M && col < N) {
        if (A[row][col] == 0) 
            replace_zero_digit(A, first_row, first_col, row, col);

        row++;
        col++;
    }
}




/* sort a matrix recursively. */
void sort_matrix_recur(int A[M][N], int row, int col)
{
    int col_with_one = -1;
    int i;

    if (row >= M || col >= N) {
        replace_zero_diag(A);
        return;
    }

    if (A[row][col] != 1) {
        /* search outer topmost row for 1 digit */
        for (i = col; i < N && col_with_one == -1; ++i) {
            if (A[row][i] == 1)
                col_with_one = i;
        }
       
        if (col_with_one != -1) {
            swap_col(A, col, col_with_one);
        } 
          
    }

    sort_matrix_recur(A, row + 1, col + 1);
}


void sort_matrix(int A[M][N])
{
    sort_matrix_recur(A, 0, 0);
}

int valid_matrix(int A[M][N])
{
    int i;

    for (i = 0; i < M; ++i)
        if (A[i][i] != 1)
            return 0;

  
    return 1;
}



int main(void)
{
    int A[M][N] = {{1, 0, 1, 0, 0},
                   {1, 1, 0, 1, 0},
                   {0, 1, 1, 1, 0},
                   {0, 1, 0, 0, 0},
                   {0, 0, 1, 1, 1}};

    print_matrix(A);
    sort_matrix(A);
    print_matrix(A);

    return 0;
}

 

(Insert Neo/Trinity/Morpheus Matrix joke here)

Please Register or Log in to view the hidden image!

 

It's not a different problem. This question is just finding a System of Distinct Representatives of a collection of sets (aka the marriage problem). This was posted in the physics/math forum:
http://www.sciforums.com/showthread.php?t=36111&highlight=matrix sorting

Swapping rows is relabelling your sets, swapping columns is relabelling your elements. If you can solve the problem with row and column swaps, it gives you an SDR of your sets, which you can trace back and give in terms of the original labels. Now re-order your (original) sets according to the number of their representative, and you've "sorted" your matrix with only row swaps.


See:
http://www.cut-the-knot.org/arithmetic/marriage.shtml

for an algorithm on finding an SDR (it uses row and column swaps, and it's thinking of sets as columns and elements and rows, the transpose of my formulation above, but not fundamentally different).

http://www.cut-the-knot.org/arithmetic/MarriageApplet.shtml

has a java implementation if you want to watch the algorithm in action.

 

Interesting...looks like you're right.