∑ Back to Perl-Python Tutorial.

General Function For Matrix Sorting

Xah Lee, 2005-03-22

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']]
↓

Python

(The Python solution was incorrect and withdrawn).

Perl

In the following perl version, i wrote around 1999, the approach is drastically different than the python version above. Instead of 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. 

# perl

=pod

sort_matrix( $matrix, [[$n1, $stringQ, $directionQ], [$n2, $stringQ,
$directionQ], ...]) sorts a matrix by $n1 th column then $n2 th...and
so on.

$matrix must be a reference to references of arrays, having the form
[[$e1, $e2,...], [...], ...].  $stringQ is a boolean indicating
whether to treat corresponding columns as a strings instead of as
number in the sorting process. True means string. $directionQ is a
boolean indicating ascending sort or not for the correpsonding
column. In the column spec $n1 $n2 ..., index counting starts at 0.

 Example:

 my $ref_matrix =
 [
   [3, 99, 'a'],
   [2, 77, 'a'],
   [1, 77, 'a']
 ];

sort_matrix( $ref_matrix,  [ [2,1,1], [1,0,1] ]);
# this means sort by third column, regarding it as strings, 
# and in ascending order. If tie, sort by second column, 
# regarding it as number, in ascending order.

# returns [[2,77,'a'],[1,77,'a'],[3,99,'a']];

=cut


sub sort_matrix($$) {
    my $ref_matrix = $_[0];
    my @indexMatrix = @{$_[1]};

    my @indexes = map {$_->[0]} @indexMatrix;
    my @operators = map {$_->[1] ? ' cmp ' : ' <=> '} @indexMatrix;
    my @directions = map {$_->[2]} @indexMatrix;

    my $body_code = '';
    my @body_array;
    for (my $i = 0; $i <= $#indexes; $i++) {
        if ($directions[$i]) {
            push(@body_array, "(\$a->[$i]" . $operators[$i]  . "\$b->[$i])");
        } else {
            push(@body_array, "(\$b->[$i]" . $operators[$i]  . "\$a->[$i])");
        };
    };
    $body_code = join( ' or ', @body_array);

    my $array_code = '(map { [' . join(q(, ), map {"\$_->[$_]"} @indexes) . ', $_]} @$ref_matrix)';

    my $code = "map {\$_->[-1]} (sort { $body_code} $array_code)";
    my @result = eval $code;
    return [@result];
};

See also:

∑ Back to Perl-Python Tutorial.
Page created: 2005-03.
© 2005 by Xah Lee.
Xah Signet