Prev: winqueryreg
Next: convert video as .wmv to . avi format
From: Rune Allnor on 22 Feb 2010 14:02
On 22 Feb, 15:44, "Jack Branning" <jbr.nos...(a)nospam.com> wrote:
> > > SORT is an obvious first candidate... you would need to
> > > call it recursively on the columns, though.
>
> > > Rune
>
> Actually, I'm now wondering if "sort" is the right function for lexicographical ordering.  I am trying to implement something from a paper, which reads:
>
> "To identify the identical rows, the rows of the matrix A are lexicographically ordered (as B×B integer tuples). This can be done in MNlog2(MN) steps. The matching rows are easily searched by going through all MN rows of the ordered matrix A and looking for two consecutive rows that are identical."
>
> where BxB represents a 3x3 sliding window...
>
> I can't seem to find a good definition of lexicographical ordering that can be applied to this context.  Does anyone have any ideas?

Lexicographic ordering is the ordering as it is done with
text: First sort the whole set based on the first letter
in each string. Then find subsets of strings that start
with the same letter, and sort on the second letter, if
one exists.

And so on.

Lexicographic sorting of matrix rows follow the same pattern:
First sort based on the values of the first row. Any subsets
of rows that share first column values are then sorted based
on the 2nd column. Then the 3rd, etc, till there are only
one row in each subset.

You can do that based on SORT, with only a tiny bit of tinkering.

Rune
From: Oleg Komarov on 22 Feb 2010 14:15
Nathan <ngreco32(a)gmail.com> wrote in message <77a99425-7ecf-4f47-8bcb-15414f6ede6b(a)u19g2000prh.googlegroups.com>...
> On Feb 22, 10:07 am, "Oleg Komarov"
> <oleg.komarovRemove.t...(a)hotmail.it> wrote:
> > "Jan Simon" <matlab.THIS_Y...(a)nMINUSsimon.de> wrote in message <hlueft$t4...(a)fred.mathworks.com>...
> > > Dear Jack!
> >
> > > > I've done some more research, and as far as I can tell, lexicographical ordering (when applied to integers) would convert:
> >
> > > > 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
> > > > to
> > > > 1, 10, 11, 12, 2, 3, 4, 5, 6, 7, 8, 9
> >
> > > It would be helpful, if you try to obtain such important information *before* you ask questions and let the NG members spend time for replies.
> >
> > >   T = [1, 5, 6, 7, 8, 9, 10, 11, 12, 2, 3, 4]
> > >   x = [2, 10, 1, 12, 4, 7]
> > >   xT = T(x);
> > >   [dum, SortInd] = sort(xT);
> > >   xLex = x(SortInd)
> >
> > > But I still have the impression it could be done easier. Jan
> >
> > % Just sorting the whole T
> > T = [1, 5, 6, 7, 8, 9, 10, 11, 12, 2, 3, 4];
> > [T, SortInd] = sort(T);
> > xLex = T(SortInd)
> > xLex =
> >      1    10    11    12     2     3     4     5     6     7     8     9
> >
> > Which is the solution given by Jan.
> >
> > Oleg
>
> Can you explain to me why THAT is the correct solution? To me, it
> looks like a trivial case. My way, although maybe not the fastest,
> DOES work as a general solution.
>
> -Nathan
If you're asking me your solution is as good as Jan's, inputs differ.

Oleg
From: Bruno Luong on 22 Feb 2010 14:21
Rune Allnor <allnor(a)tele.ntnu.no> wrote in message <87dbd1e7-d0a6-4cd9-93d5-81a522bcdcd6(a)g10g2000yqh.googlegroups.com>...

>
> Lexicographic ordering is the ordering as it is done with
> text: First sort the whole set based on the first letter
> in each string. Then find subsets of strings that start
> with the same letter, and sort on the second letter, if
> one exists.
>
> And so on.
>
> Lexicographic sorting of matrix rows follow the same pattern:
> First sort based on the values of the first row. Any subsets
> of rows that share first column values are then sorted based
> on the 2nd column. Then the 3rd, etc, till there are only
> one row in each subset.
>
> You can do that based on SORT, with only a tiny bit of tinkering.
>
> Rune

This is a very inefficient way to carry out lexicography sorting.

Sort by whole last column first, then go up to the first column. No need to make expensive recursive calls. This works because Matlab SORT is a stable algorithm.

Or better yet, use SORTROWS command (why reinvent the whell?).

Bruno
From: Matt Fig on 22 Feb 2010 16:50
Nathan <ngreco32(a)gmail.com> wrote in message <77a99425-7ecf-4f47-8bcb-
> Can you explain to me why THAT is the correct solution? To me, it
> looks like a trivial case. My way, although maybe not the fastest,
> DOES work as a general solution.
>
> -Nathan

Even more general, since an array was the original focus:


% Data
T = ((rand(3,5)*5));

% Engine
A = arrayfun(@(x) sprintf('%.15f',x),T,'Un',0);
for ii = 1:size(A,1)
A(ii,:) = sort(A(ii,:));
end
A = str2double(A);
From: us on 22 Feb 2010 18:37
"Oleg Komarov"
> % Just sorting the whole T
> T = [1, 5, 6, 7, 8, 9, 10, 11, 12, 2, 3, 4];
> [T, SortInd] = sort(T);
> xLex = T(SortInd)
> xLex =
> 1 10 11 12 2 3 4 5 6 7 8 9
>
> Which is the solution given by Jan.
>
> Oleg

bad news - and - carefully look at this particular T(!)...
- in general, this approach certainly cannot work...

v=1:12; % another T...
[v,vx]=sort(v);
vlex=v(vx)
% vlex = 1 2 3 4 5 6 7 8 9 10 11 12

us
First  |  Prev  |  Next  |  Last
Pages: 1 2 3 4 5
Prev: winqueryreg
Next: convert video as .wmv to . avi format