Hi,
On Sat, Aug 22, 2009 at 2:45 PM, Michael Kogan wrote:
> Hi,
>
> I need to compare two matrices with each other. If you can get one of them
> out of the other one by resorting the rows and/or the columns, then both of
> them are equal, otherwise they're not. A matrix could look like this:
>
> [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
> [1,] 0 1 1 1 0 1 1 0
> [2,] 1 1 0 0 0 1 0 1
> [3,] 1 0 1 0 0 0 1 1
> [4,] 1 1 0 0 1 0 0 0
> [5,] 1 0 1 1 1 0 0 0
> [6,] 0 1 0 1 1 0 0 0
> [7,] 0 0 0 0 0 1 1 1
>
> Note that each matrix consists of ones and zeros, in each row and in each
> column there are at least three ones and one zero and each pair of
> rows/columns may have at most two positions where both are ones (e.g. for
> the 1. and 2. rows those positions are 2 and 6).
>
> I was advised to sort both matrices in the same way and then to compare
> them element by element. But I don't manage to get them sorted... My
> approach is as following:
>
> 1. Sort the rows after the row sums (greater sums first).
> 2. Sort the columns after the first column (columns with ones in the first
> row go left, columns with zeros go right).
> 3. Save the left part (all columns with ones in the first row) and the
> right part in separate matrices.
> 4. Repeat steps 2 and 3 with both of the created matrices (now taking the
> second row for sorting), repeat until all fragments consist of a single
> column.
> 5. Compose the columns to a sorted matrix.
>
> This algorithm has several problems:
>
> 1. How to make a loop that is branching out in two subloops on each
> iteration?
> 2. How to organize the intermediate results and compose them without losing
> the order? Maybe save them in lists and sublists?
> 3. A fundamental problem: If there are rows with equal sums the result may
> depend on which of them is sorted after first. Maybe this algorithm won't
> work at all because of this problem?
Ouch, this seems like a real PITA.
If you want to go about this by implementing the algo you described, I think
you'd be best suited via some divide-and-conquer/recursion route:
http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm
Perhaps you can take inspiration from some concrete sorting algorithms that
are implemented this way:
Merge sort: http://en.wikipedia.org/wiki/Merge_sort
Quick sort: http://en.wikipedia.org/wiki/Quicksort
Hope that helps,
-steve
--
Steve Lianoglou
Graduate Student: Computational Systems Biology
| Memorial Sloan-Kettering Cancer Center
| Weill Medical College of Cornell University
Contact Info: http://cbio.mskcc.org/~lianos/contact
[[alternative HTML version deleted]]