Re: general function for sorting a matrix
hi, just a quick reply. You are right, the python version i have is really terrible. I'll look at your solution and possibly reply later. Thanks for your code. It's great! Xah On Aug 29, 9:40 am, Marc 'BlackJack' Rintsch [EMAIL PROTECTED] wrote: On Wed, 29 Aug 2007 08:47:27 -0700,XahLeewrote: 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 ofsortingby looping thru the sortingdirectives, 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 don't see why that is more functional. After all you iterate in both versions through the directives. In Perl to build the code, in Python to sort the list multiple times. Here's a Python function that sorts the list just once: def sort_matrix(matrix, directives): tmp = [(column - 1, str if as_string else float, 1 if ascending else -1) for (column, as_string, ascending) in directives] def cmp_func(row_a, row_b): for column, convert_func, factor in tmp: result = cmp(convert_func(row_a[column]), convert_func(row_b[column])) * factor if result: return result return 0 matrix.sort(cmp=cmp_func) There's no return value as your reference implementation sorts in place too. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
general function for sorting a matrix
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 [EMAIL PROTECTED] ∑ http://xahlee.org/ -- http://mail.python.org/mailman/listinfo/python-list
Re: general function for sorting a matrix
On Wed, 29 Aug 2007 08:47:27 -0700, Xah Lee wrote: 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 don't see why that is more functional. After all you iterate in both versions through the directives. In Perl to build the code, in Python to sort the list multiple times. Here's a Python function that sorts the list just once: def sort_matrix(matrix, directives): tmp = [(column - 1, str if as_string else float, 1 if ascending else -1) for (column, as_string, ascending) in directives] def cmp_func(row_a, row_b): for column, convert_func, factor in tmp: result = cmp(convert_func(row_a[column]), convert_func(row_b[column])) * factor if result: return result return 0 matrix.sort(cmp=cmp_func) There's no return value as your reference implementation sorts in place too. Ciao, Marc 'BlackJack' Rintsch -- http://mail.python.org/mailman/listinfo/python-list
Re: general function for sorting a matrix
Xah Lee wrote: [undermotivated blah stripped] don't feed the troll. Stefan -- http://mail.python.org/mailman/listinfo/python-list
Re: general function for sorting a matrix
On 2007-08-29, Xah Lee [EMAIL PROTECTED] wrote: 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. The advantage of such a richly implemented language as Python, is that a programmer don't need to write a general sorting algorithm at all. -- Neil Cerutti -- http://mail.python.org/mailman/listinfo/python-list