matrix sorting problem

Discussion in 'Computer Science & Culture' started by Fallen Angel, May 13, 2004.

Thread Status:
Not open for further replies.
  1. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
    EDIT: see few posts below for clarification of this problem statement

    Here's a problem I've been laboring over on and off for a few years now. Perhaps you peoples can shed some insight.

    The goal is to sort a matrix of 1s and 0s so all the 1s are on the diagonal.
    example..

    start with something like:

    0 1 1 0 1 0 0 1
    1 0 1 1 0 0 1 0
    0 1 1 0 0 1 0 1
    0 1 1 1 0 1 1 0
    0 0 0 0 1 0 0 1
    0 1 0 0 0 1 0 0
    1 0 0 0 0 0 0 0
    0 0 0 1 1 0 0 0

    and end up with something to the effect of:

    1 0 0 0 0 0 0 0
    0 1 0 0 0 1 0 0
    1 0 1 1 0 0 1 0
    0 0 0 1 1 0 0 0
    0 1 1 0 1 0 0 1
    0 1 1 1 0 1 1 0
    0 1 1 1 0 1 1 0
    0 0 0 0 1 0 0 1

    The trick is to do it in nonexponential time. And most preferable in linear time.
    Basically O(n). If anyone knows of a published work that addresses this problem, or if you know of an algorithm to solve this, any help would be greatly appreciated.
     
    Last edited: May 13, 2004
  2. Google AdSense Guest Advertisement



    to hide all adverts.
  3. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
    sorry bout that.. but the font turned out bad on the matrices.. but you get what i mean
     
  4. Google AdSense Guest Advertisement



    to hide all adverts.
  5. malkiri Registered Senior Member

    Messages:
    198
    You might want to give a more specific statement of the problem. My first reaction is to use dynamic programming. It's not my strongest area, so I'll have to think about how to structure it. What complexity is the brute force approach?
     
  6. Google AdSense Guest Advertisement



    to hide all adverts.
  7. Blindman Valued Senior Member

    Messages:
    1,425
    Ill assume that every column has at least one 1 else there is no solution..

    Next each column represents a binary number, represented by the value V[a]. a = column number starting with column 0. Column 1 is V[0], then V[1], V[2].. etc..

    We then know that the first column must represent a binary number that is V[0] >= 1 then next must be V[1]>= 2 then V[2]>= 4 and so forth to the last which must be V[n-1]>= 2^(n-1), n= number of columns.

    We can then test each column to see if a one is in the correct position. If V[a]&(2^(a-1)) > 0 then do nothing as 1 is in the correct position. (& represents boolean AND).

    If I was coding it I would simple move all the ones up one by dividing by 2. Of course I would also have to move the bit at the top of the column to the bottom. This can be achieved with the statement V[a] = (V[a]/2) + (V[a]&1)*(2^n-1). Do this until V[a]&(2^(a-1)) > 0. Do this for each column.

    The maximum number of iterations would be n*(n-1) the minimum would be n with an average of n*(n/2-1), (could be wrong about the average).

    This is a long way from 0(n) but that is impossible. 1(n) is the minimum number of iterations required to solve the problem because you have to test each column at least once to see if it is in the right position.

    With a bit more thought you could shift the bits both up and down depending on where the closest on bit is. But I need to sleep.

    One last thing, this is just of the top of my head so let me know if Im full of it

    Please Register or Log in to view the hidden image!

    . Another solution is to use a neural net. The average number of iterations could be reduced in the net especially if you would accept an error rate. If the output of the net is wrong do it again. With a n-2 layered net you could get a average of about n*(n/2-2)+n*errorRate+(n-1)*errorRate+(n-2)*errorRate.....(n-(n-1))*errorRate. ErrorRate = number of errors/n. I cant be bothered to calculate the number of errors for the n-? layered net. Plus checking the output would add n iterations to the calculation but this could be done in parallel. Of course the net could totally fail which would make the average meaningless.

    Yawn.. Thank for the interesting problem I'm sure ill dream about it and maybe have a better solution in the morning.
     
  8. malkiri Registered Senior Member

    Messages:
    198
    I'm not sure this is the same problem. It seems to me he's asking for the rows of the matrix to be sorted such that there's a diagonal of ones. Look closely at the example...the order of bits in each of the rows is preserved from input to output. It sounds like your algorithm moves bits individually instead of moving the entire row together. If the rows do need to be preserved, that makes the problem much harder as you don't know whether you should have a row like 10001 at the top or bottom of the matrix - you may not have any more rows with a 1 in the first position, or you may not have any more with a 1 in the last position.

    I do notice only one row that has changed from input to output (0 1 1 0 0 1 0 1 to 0 1 1 0 1 0 0 1). Is that a mistake?
     
    Last edited: May 13, 2004
  9. Blindman Valued Senior Member

    Messages:
    1,425
    Not rows.. Columns. Not that it changes the problem...
     
  10. Blindman Valued Senior Member

    Messages:
    1,425
    Opps.. Its late.. Your right malkiri it is all over the place. Disregard my first post because i have not idea now what he wants..
     
  11. malkiri Registered Senior Member

    Messages:
    198
    I understand that your algorithm looks at the values of the columns. What I'm saying is that in the following:

    you seem to be moving individual bits as opposed to an entire row (or an entire column). If we're sorting the matrix rows as it seems in the problem, then the decimal values of the rows must stay the same, even if the position of the row in the matrix moves. Same for a column, if you look at it that way. The above step of your algorithm changes these values.
     
  12. Blindman Valued Senior Member

    Messages:
    1,425
    Oh will I ever get to bed... It looks like he is sorting rows so that the bits go diagonal. This sugests that the rows cant be totaly random because most combinations have no solution.. Anyway thats is for me.
     
  13. Stryder Keeper of "good" ideas. Valued Senior Member

    Messages:
    13,105
    I would suggest looking at "Transformation" matrix mathematics in relation to 3D Graphics and programming, afterall your looking to "Transform" your first matrix to match that of a predefined "Identity" Matrix.

    An identity matrix in your case would be:
    Code:
    1 0 0 0 0 0 0 0
    0 1 0 0 0 0 0 0
    0 0 1 0 0 0 0 0
    0 0 0 1 0 0 0 0
    0 0 0 0 1 0 0 0
    0 0 0 0 0 1 0 0
    0 0 0 0 0 0 1 0
    0 0 0 0 0 0 0 1
    
    Usually it involves Multiplying a number by the position's within the matrix. (You have to note that each position is defined like a grid reference, and the data parsed to it has to be aligned with those references.)

    Why it works, simple:
    0 x 1 = 0
    1 x 1 = 1 // This would mean it fits.
    1 x 0 = 0

    more detailed explainations can be found on the web if you look for "3D Graphic Matrix Mathematic Tutorial" (It will help you visualise it too)

    These links should help:
    http://pages.infinit.net/jstlouis/3dbhole/mathematics_of_3d_graphics.html
    http://www.microtonal.co.uk/matritut.htm
     
  14. malkiri Registered Senior Member

    Messages:
    198
    This isn't what he's asking for, either...the output of his example has a diagonal of ones, but it's not an identity matrix. Again, it seems to me he's sorting the rows of the matrix such that it creates a diagonal of ones. Simply creating an identity matrix is trivial.
     
  15. curioucity Unbelievable and odd Registered Senior Member

    Messages:
    2,429
    Gosh.... I'm totally suck at this level of Algorith.......
    I just though of row-by-row check-n-swap (check first element of first row, 1=keep then go to next row check 2, 0=next row), but that would be a O(n^2)..... grrr....
     
  16. malkiri Registered Senior Member

    Messages:
    198
    It also would fail on this input:

    Code:
    10001
    00110
    10000
    01100
    01010
    
    Assuming you start from the top left, it'll see the first 1 and leave that row where it is. Then once it gets down to the very last row, it won't have any available rows with a 1 in the last position.

    Edit:
    Incidentally, O(n^2) isn't that bad. The original poster asked for an algorithm that's non-exponential. O(n^2) is polynomial time. An example of exponential time is O(2^n).
     
  17. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
    Yeah... sorry, I was out for a bit and haven't read all of it yet.. but malkiri is correct in that i am looking to sort rows of 0s and 1s into a matrix with ones on the diagonal.

    and yes malkiri, the input to output change there was a mistake... more as i read through the posts
     
  18. Fallen Angel life in every breath Registered Senior Member

    Messages:
    189
    Ok, read the whole thing. Sorry about the whole confusion about the statement of the problem. I've had this on my mind for so long that I didn't state all the conditions. Once again, my apologies.

    malkiri got the jist/gest? the idea of what the problem is.

    take a square matrix with rows that have at least one 1 in them.
    sort the square matrix in such a fasion that... now this is the important part:

    if there exists in any row, a 1 in column x, then the final sorted matrix needs to have
    a 1 on the diagonal in that column. for example..

    0100 there is a 1 in the second column, therefore in the final sorted matrix, there
    needs to be a 1 on the diagonal in the second column like so...('a' is space filler)

    aaaa
    a1aa
    aaaa etc..

    the rows cannot change, but they can change their position vertically.

    also, clarification on complexity.
    non-exponential complexity is what i am looking for. that is, polynomial time would be a good solution (as in O(n^2)).

    malkiri, the brute force is O(2^n) if i remember correctly. ADDITIONALY, it is important that SPACIAL complexity is also polynomial. Some of the solutions I've had worked out (if my memory serves me right, i dug up this problem recently) in polynomial time, but the spacial complexity just was way out there.
     
  19. okinrus Registered Senior Member

    Messages:
    2,669
    0 1 1 0 1 0 0 1
    1 0 1 1 0 0 1 0
    0 1 1 0 0 1 0 1
    0 1 1 1 0 1 1 0
    0 0 0 0 1 0 0 1
    0 1 0 0 0 1 0 0
    1 0 0 0 0 0 0 0
    0 0 0 1 1 0 0 0


    Determine which rows match which column, that is have one's. O(n^2)
    0-> 1 6
    1-> 0 2 3 5
    2-> 0 1 2 3
    3-> 1 3
    4-> 0 4 7
    5-> 2 3 5
    6-> 1 3
    7-> 0 2 4

    This should form a graph with all the data necessary to solve the problem. Each transition from one vertex to another means that the from vertex be swapped with the to vertex, and we are therefore looking for a path of length 7(we know we must make 7 swaps) and where no node is repeated more than once.

    Here, I'm not too sure how to solve it efficiently. Possibly remove the cycles and generate a dependency graph. I don't think your getter better results in the worst case by working from avenues since I believe the graph expresses nothing more than all of the information of the problem that is necessary to solve the worst case.
     
  20. Stryder Keeper of "good" ideas. Valued Senior Member

    Messages:
    13,105
    Malkiri,
    You use an identity matrix so that you can change your ruleset if you want at a later date. This means making your program cable of being altered easily in the future, rather than having to reprogram everything to deal with a new pattern.
     
  21. malkiri Registered Senior Member

    Messages:
    198
    Identity matrices have nothing to do with this problem. It just so happens that he wants the ones to lie along the same diagonal. It would be the same problem if the ones were to go along the other diagonal, and that's obviously not an identity matrix. "Using" an identity matrix, however you would do that in the context of this problem, doesn't make the solution any more flexible.
     
  22. malkiri Registered Senior Member

    Messages:
    198
    okinrus:

    That's an interesting approach...I think this is a step in the right direction. I'm not sure I quite understand this part:

    Unless I'm not correctly understanding how you're creating the graph, what you're actually looking for is a graph with cycles - that is, you want each of the nodes to reference itself, meaning that column has a one in the corresponding row.

    We also don't necessarily need to make N swaps, unless you count swapping a row with itself (thus leaving it in place) as a swap.

    Let's reduce the problem to a less complicated input:

    Code:
    0010
    1000
    0100
    0001
    0 -> 1
    1 -> 2
    2 -> 0
    3 -> 3

    The graph of the solution would look like:

    0 -> 0
    1 -> 1
    2 -> 2
    3 -> 3

    In the context of this input, row swapping like you suggested makes sense. We might first swap row 0 with row 1, then row 1 with row 2, and end up with the solution. However, on a more complicated input, how do you decide which to-node you swap the from-node with?

    Code:
    10001
    00110
    10000
    01100
    01010
    0 -> 0 2
    1 -> 3 4
    2 -> 1 3
    3 -> 1 4
    4 -> 0

    For row 0, I can leave it in place for now as it has a self reference. For row 1, do I swap it with row 3 or 4? 4 is the correct choice (see below), but 3 looks just as valid at the time.

    Solution (the only one, btw):

    Code:
    10000
    01010
    01100
    00110
    10001
    0 -> 0 4
    1 -> 1 2
    2 -> 2 3
    3 -> 1 3
    4 -> 4

    Converting the input to some sort of graph might help with this problem, but this algorithm (as I understand it) seems to be essentially the same as the greedy approach proposed by curioucity. Am I misunderstanding something?
     
Thread Status:
Not open for further replies.

Share This Page