Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Java > general function for sorting a matrix

Reply
Thread Tools

general function for sorting a matrix

 
 
Xah Lee
Guest
Posts: n/a
 
      08-29-2007
A couple years ago, i posted a programing problem, about writing a
function that will sort a arbitrarily dimentioned matrix in any
possible way to sort it.

Such a function, is rather typical in functional programing
languages. I wrote a version in 1999 in perl for practical purposes,
since sorting a matrix (i.e. list of lists) is rather common. With
this function, i can have a single interface to deal with any list
(including list of lists).

It is ideal, that a language's function for sort actually are of this
generality.
(See “What is Expressiveness in a Computer Language”, Xah Lee, 2005.
http://xahlee.org/perl-python/what_i...esiveness.html
)

The advantage of such a generality, is that a programer don't need to
write a sorting code every time she encounters a list.

Anyway, so i wrote it in 1999 in perl for practical purposes, and have
used it in industrial coding often. In 2005, while i was learning
Python, i wrote a python version as a exercise. Today, i actually
need it again, while coding in python. So i looked at my code and
spruced up the documentation.

Here's the function spec:
----------------

Today we'll write a function that can sort a matrix in all possible
ways. Following is the specification. Take a day to see if you can
write such a function in your favorite language. Perl and Python
solutions are at the end of this page.

sort_matrix( matrix, [[n1, s1, d1], [n2, s2, d2], [n3, s3, d3], ...])
returns a sorted matrix by n1 th column, if tie, then by n2 th
column ... and so on.

The first argument is a list, whose elements are lists of equal
lengths.

s1, s2, s3... are booleans. If True, then the corresponding column are
interpreted as a string and the ordering is lexicographical.

d1, d2, d3... are booleans. If True, the sort for the corresponding
column are ascending.

Example:.

myMatrix =
[
[3, 99, 'a'],
[2, 77, 'a'],
[1, 77, 'a']
];

sort_matrix(myMatrix,[[3,True,True],[2,False,True]])

This means sort by 3th column, regarding it as strings, and in
ascending order. If tie, sort by 2th column, regarding it as number,
in ascending order. It returns:

[[2,77,'a'],
[1,77,'a'],
[3,99,'a']]

----------------

While reviewing this code, there's something interesting of note.

Namely, in my perl solution, the approach is drastically different
than the python version. Instead of sorting by looping thru the
sorting directives, it parses the directives then generate the
complete sort code, then eval it in one shot. This is more of a pure
functional approach.

I thought it is of interest.

The Perl and Python solutions are at:
General Function For Matrix Sorting
http://xahlee.org/perl-python/sort_matrix.html

It would be interesting, to see a python version using the approach
i've done in the Perl version, and a Perl version using imperative
approach without using eval().

A solution in lisp (emacs lisp, common lisp, scheme) would be
relatively trivial, similarly for Haskell and Mathematica. In fact, i
think the sort function as specified above are not very useful in
practice in these languages to various degress (depending on the
lang). Because a functional language usually have powerful,
generalized functions and constructs that solve the above in a few
trivial lines that are rather ideomatic to the language.

Nevertheless, it would be interesting to see a solution in the above
languages.

For the languages i'm personally involved, a major difficulty would be
Java. In my opinion, it would be a very difficult (if not impossible)
to construct this sort function Java, C, C++, C#.

Xah
http://www.velocityreviews.com/forums/(E-Mail Removed)
http://xahlee.org/

 
Reply With Quote
 
 
 
 
Stefan Behnel
Guest
Posts: n/a
 
      08-29-2007
Xah Lee wrote:
[undermotivated blah stripped]

don't feed the troll.

Stefan
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Matrix*Vector and Vector*Matrix Holgerson C++ 3 10-26-2007 07:38 AM
general function for sorting a matrix Xah Lee Python 4 09-10-2007 01:15 PM
general function for sorting a matrix Xah Lee Perl Misc 2 08-29-2007 04:51 PM
Matrix composed by two matrix lvcargnini VHDL 3 07-05-2006 07:21 AM
Re: Matrix DTS and Matrix 2 DTS? PeterTHX DVD Video 0 08-03-2003 05:46 AM



Advertisments