[R] Help on comparing two matrices
David Winsemius
dwinsemius at comcast.net
Sat Aug 22 22:23:55 CEST 2009
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
More information about the R-help
mailing list