Advanced Search
All Posts : Product Tips & Techniques
John Fredsted asks whether there is a built-in method in Maple for lexically sorting a list of lists of small positive integers. There is not, however, Robert Israel provided two methods for accomplishing the task. The first uses the standard technique for extending Maple's sort procedure, that is, assigning a boolean-valued binary function and passing it to sort. The second method that Robert provided is ingenious. Here it is, in full, 
Ls:= map(convert,L,bytes):
Ls:= sort(Ls, lexorder):
map(convert,Ls,bytes);

It converts each list into a string, sorts the strings, then converts the strings back to lists. This method is significantly faster than the previous. It does, however, have a limitation; it can only operate on lists with positive integers in the range 1..255. While that limitation was suitable for the original poster's application, that will not always be the case.

It would be convenient to be able to shift the range of allowable consecutive integers, say to include 0. That can be readily accomplished by adding/subtracting before and after sorting, however, doing so increases the time and memory usage. There is a method to avoid some of the cost, that is, to use sorting with attributes. Here is an example showing how that can be done: 

sortlex := proc(L, inc::integer:=1)
local lst;
description
    "sort lexically a list of lists of integers; "
    "the integers must be in the range 1-inc .. 255-inc";

    map(attributes, sort([seq(setattribute(convert(map(`+`,lst,inc)
                                                   ,'bytes'),lst)
                              , lst=L)]));
end proc:
For example, 
L := RandomTools:-Generate(listlist(integer(range=-5..5), 4, 3));
              L := [[-5, -5, -3], [-1, -1, 4], [4, 4, 5], [-4, 2, -2]]

sortlex(L,6);
              [[-5, -5, -3], [-4, 2, -2], [-1, -1, 4], [4, 4, 5]]
Because this procedure can fail if the integers are outside the allowable range, it is prudent to ensure that this is case. This can be accomplished using the depends parameter modifier that was introduced in Maple 10. 
sortlex := proc(L::depends(list(list(integer[1-inc..255-inc])))
                , inc::integer:=1)
local lst;
description
    "sort lexically a list of lists of integers; "
    "the integers must be in the range 1-inc .. 255-inc"

    map(attributes, sort([seq(setattribute(convert(map(`+`,lst,inc)
                                                   ,'bytes'), lst)
                             , lst=L)]));
end proc:
For my amusement I extended Robert's technique so that it can be used with integers in the range 1-inc .. 255-1-inc. It is more efficient than list-based sorting, at least for a sufficient number of lists. Here is the code. 
sortlex8 := proc(L::depends(list(list(integer[1-inc..255^2-1-inc])))
                 , inc::integer:=1)
local lst,r;
    map(attributes, sort([seq(setattribute(convert(
        map(i -> (iquo(i+inc,255,'r')+1,r+1), lst)
        , 'bytes' ), lst)
                              , lst=L)]));
end proc:
assign convert integer

Please Wait...