[R] Help on comparing two matrices

[David Winsemius]

On Aug 22, 2009, at 3:47 PM, David Winsemius wrote:

>
> On Aug 22, 2009, at 3:36 PM, Steve Lianoglou wrote:
>
>> Hi,
>>
>> On Sat, Aug 22, 2009 at 2:45 PM, Michael Kogan  
>> <michael.kogan at 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.
>
> Well, I certainly agree with that.
>
> Why not sort by a concatenation of the rows and then see if they are  
> equal:
>
> sm <- matrix(scan(textConnection("
> 0    1    1    1    0    1    1    0
> 1    1    0    0    0    1    0    1
> 1    0    1    0    0    0    1    1
> 1    1    0    0    1    0    0    0
> 1    0    1    1    1    0    0    0
> 0    1    0    1    1    0    0    0
> 0    0    0    0    0    1    1    1")), 7, 8)
>
> > sm[order(sapply(1:7, function(x) Reduce(paste, smt[x,])) ), ]
                                                   ^sm^
Had earlier made a copy before concatenation, but it proved superfluous.

>     [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8]
> [1,]    0    0    0    0    1    1    0    0
> [2,]    0    0    1    1    1    0    0    1
> [3,]    1    0    0    0    0    0    0    1
> [4,]    1    0    0    1    0    0    0    0
> [5,]    1    1    0    0    1    1    0    1
> [6,]    1    1    1    1    0    0    1    0
> [7,]    1    1    1    1    0    1    1    0
>
> Then an identical() test on the sorted matrices?
>
>
>>
>> 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
>>
>
> David Winsemius, MD
> Heritage Laboratories
> West Hartford, CT
>
> ______________________________________________
> R-help at 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.

David Winsemius, MD
Heritage Laboratories
West Hartford, CT