On Aug 22, 2009, at 3:36 PM, Steve Lianoglou wrote:
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.
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
______________________________________________
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.
