Matrix sorting

Discussion in 'Computer Science & Culture' started by okinrus, Aug 29, 2004.

Thread Status:
Not open for further replies.
  1. okinrus Registered Senior Member

    Messages:
    2,669
    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
    
     
    Last edited: Aug 29, 2004
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Stryder Keeper of "good" ideas. Valued Senior Member

    Messages:
    13,104
    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)
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. okinrus Registered Senior Member

    Messages:
    2,669
    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.
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Stryder Keeper of "good" ideas. Valued Senior Member

    Messages:
    13,104
    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.
     
  8. okinrus Registered Senior Member

    Messages:
    2,669
    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.
     
  9. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
    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!

     
  10. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
  11. okinrus Registered Senior Member

    Messages:
    2,669
    Ok, I'll also write some C code to test this out.
     
  12. malkiri Registered Senior Member

    Messages:
    198
    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
     
  13. okinrus Registered Senior Member

    Messages:
    2,669
    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.
     
  14. malkiri Registered Senior Member

    Messages:
    198
    There's no column swap in the original problem. Allowing that results in a completely new problem definition and solution.
     
  15. okinrus Registered Senior Member

    Messages:
    2,669
    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.
     
  16. malkiri Registered Senior Member

    Messages:
    198
    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.
     
  17. okinrus Registered Senior Member

    Messages:
    2,669
    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;
    }
    
     
  18. cckieran HighSchool Phys/Chem student Registered Senior Member

    Messages:
    60
    (Insert Neo/Trinity/Morpheus Matrix joke here)

    Please Register or Log in to view the hidden image!

     
  19. shmoe Registred User Registered Senior Member

    Messages:
    524
    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.
     
  20. malkiri Registered Senior Member

    Messages:
    198
    Interesting...looks like you're right.
     
Thread Status:
Not open for further replies.

Share This Page