general function for sorting a matrix

Discussion in 'Java' started by Xah Lee, Aug 29, 2007.

  1. Xah Lee

    Xah Lee Guest

    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_is_expresiveness.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://xahlee.org/
    Xah Lee, Aug 29, 2007
    #1
    1. Advertising

  2. Xah Lee wrote:
    [undermotivated blah stripped]

    don't feed the troll.

    Stefan
    Stefan Behnel, Aug 29, 2007
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. lvcargnini

    Matrix composed by two matrix

    lvcargnini, Jul 4, 2006, in forum: VHDL
    Replies:
    3
    Views:
    2,644
    Jonathan Bromley
    Jul 5, 2006
  2. Xah Lee
    Replies:
    4
    Views:
    365
    Xah Lee
    Sep 10, 2007
  3. Holgerson

    Matrix*Vector and Vector*Matrix

    Holgerson, Oct 25, 2007, in forum: C++
    Replies:
    3
    Views:
    396
    Holgerson
    Oct 26, 2007
  4. Mike Oliver
    Replies:
    0
    Views:
    384
    Mike Oliver
    Feb 1, 2011
  5. Xah Lee

    general function for sorting a matrix

    Xah Lee, Aug 29, 2007, in forum: Perl Misc
    Replies:
    2
    Views:
    186
    Stefan Behnel
    Aug 29, 2007
Loading...

Share This Page