Hi, On Sat, Aug 22, 2009 at 2:45 PM, Michael Kogan <michael.ko...@gmx.net>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]] ______________________________________________ R-help@r-project.org mailing list https://stat.ethz.ch/mailman/listinfo/r-help PLEASE do read the posting guide http://www.R-project.org/posting-guide.html and provide commented, minimal, self-contained, reproducible code.
