[R] Help on comparing two matrices

[David Winsemius]

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,])) ), ]
      [,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