Ordering a list of lists

Posted on 2007-10-26 12:01 By John Fredsted ( Maple Rating 4

566)

Categories:

Consider, just a test example, the following list of lists of positive integers ordered ascendingly

L := [[1,2,7,12],[3,4,5,6],[1,2,5,9]];

I would like this list of lists ordered so that [1,2,5,9] precedes [1,2,7,12], because 5 < 7 (the first two elements being equal), and [1,2,7,12] precedes [3,4,5,6], because 1 < 3. I think you see the general scheme. That can be achieved with the following code:

with(ListTools):
swapLists := proc(L1::'list'(posint),L2::'list'(posint))
   local L;
   L := MakeUnique(L1-L2);
   if L = [0] then
      false
   elif L[1] <> 0 then
      L[1] < 0
   else
      L[2] < 0
   end if
end proc:
sort(L,swapLists);

My question is: does there exist some smarter way?

Lexicographic order

Comment on 2007-10-26 17:10 from Robert Israel ( Maple Rating 4

1460)

> lex:= proc(L1,L2) 
    local n;
    for n from 1 to min(nops(L1),nops(L2)) do
      if L1[n] <> L2[n] then return(evalb(L1[n] < L2[n]))
      end if
    end do;
    evalb(nops(L2) > nops(L1))
  end proc;
  sort(L, lex);

It would be nice if a "lexicographic order" for lists of integers were built-in, as it is for lists of symbols or strings, but apparently this is not the case. For lists of symbols, you could just say sort(L, lexorder).

If all the entries of your lists are integers from 1 to 255 you could say

> Ls:= map(convert,L,bytes):
  Ls:= sort(Ls, lexorder):
  map(convert,Ls,bytes);

Clean and faster

Comment on 2007-10-27 04:37 from John Fredsted ( Maple Rating 4

566)

Thanks for your cleverly designed code which is both cleaner and faster than my code is.

I am happy to read that you too have been unable to find any built-in functionality (something like "lexicographic ordering for integers") because that tells me that I have not overlooked something embarrasing simple.

You second suggestion is actually quite useful to me if, as seems rather reasonable, I disallow spacetime dimensionalities (in the package "SpaceTime" on which I am working) to exceed 255.

Even for string/M-theory 255 spacetime dimensions should be sufficient, but who knows what those immensely mathematically gifted, but also, so it seems, at the same time increasingly out of contact with physical reality, guys in string/M-theory cook up next?! I cannot resist here quoting the famous put-down by Wolfgang Pauli concerning string-theory: "It's not even wrong."

ordering a list of lists

Comment on 2007-10-26 17:49 from xavier (

30)

I am working on Maple 7.
I think I found a way to do what you want.
It is the procedure f:you must put 1 for the second argument.

f := proc (l, k) local n, A, B, ki, AA, d, kk, r, kki, BB; if l = [] then l else if k = max(seq(nops(l[i]),i = 1 .. nops(l)))+1 then l else n := min(seq(l[i][k],i = 1 .. nops(l))); A := []; B := []; for ki to nops(l) do if l[ki][k] = n then A := [op(A), l[ki]] else B := [op(B), l[ki]] end if end do; AA := []; d := sort(convert({seq(nops(A[i]),i = 1 .. nops(A))},list)); for kk to nops(d) do r := []; for kki to nops(A) do if nops(A[kki]) = d[kk] then r := [op(r), A[kki]] end if end do; AA := [op(AA), r] end do; BB := []; d := sort(convert({seq(nops(A[i]),i = 1 .. nops(A))},list)); for kk to nops(d) do r := []; for kki to nops(B) do if nops(B[kki]) = d[kk] then r := [op(r), B[kki]] end if end do; BB := [op(BB), r] end do; return [seq(op(f(AA[ti],k+1)),ti = 1 .. nops(AA)), seq(op(f(BB[ti],k)),ti = 1 .. nops(BB))] end if end if end proc;

f([[1,2,7,12],[3,4,5,6],[1,2,5,9]],1);
[[1, 2, 5, 9], [1, 2, 7, 12], [3, 4, 5, 6]]

Is it simpler?

Comment on 2007-10-27 04:47 from John Fredsted ( Maple Rating 4

566)

Thanks a lot for the apparently extensive work you have done on this problem of mine. However, please forgive me for saying so, I do not think that it represents a simpler solution to the problem than mine does.

ordering a list of lists (a mistake in f)

Comment on 2007-10-27 06:03 from xavier (

30)

Sorry,I made a mistake in f :f doesn't work with a list of lists which have differents lengths.
here is a new procedure f that seems working:

f:=proc(l,k);if l=[] then l else if k=max(seq(nops(l[i]),i=1..nops(l)))+1 then l;else n:=min(seq(l[i][k],i=1..nops(l)));A:=[];B:=[];for ki from 1 to nops(l) do if l[ki][k]=n then A:=[op(A),l[ki]];else B:=[op(B),l[ki]];fi;od;AA:=[];AB:=[];for kk from 1 to nops(A) do if nops(A[kk])>=k+1 then AA:=[op(AA),A[kk]];else AB:=[op(AB),A[kk]];fi;od;return([op(AB),op(f(AA,k+1)),op(f(B,k))]);fi;fi;end;

f([[2,1],[2,2],[2,1,3]],1);
[[2, 1], [2, 1, 3], [2, 2]]
f([[1,2,7,12],[3,4,5,6],[1,2,5,9]],1);
[[1, 2, 5, 9], [1, 2, 7, 12], [3, 4, 5, 6]]
(f is still a little complex but doesn't use 'sort')

A bit complex

Comment on 2007-10-27 07:39 from John Fredsted ( Maple Rating 4

566)

Thanks again for the suggestion of yours. However, as you mention yourself, the procedure seems somewhat complex. And even though it treats list of lists of various lengths, as does also the code by Robert Israel, and it does not use sort(), these issues were not the intention of the originally posed problem of mine.

sorting lists of lists

Comment on 2008-03-21 15:00 from dpinto (3)

Here's maybe an easier way ...

L:=sort(L,(a,b)->evalb(a[1]<b[1]));

This will sort on the first element of each list where L is a list of lists.

doesn't work

Comment on 2008-03-21 15:54 from Joe Riel ( Maple Rating 4

1258)

That doesn't work. It only sorts on the first element of a list. Try it with, say,

L := [[1,2],[1,1]];

Easy fix

Comment on 2008-03-21 16:43 from dpinto (3)

You're right, of course.

Comment on 2008-03-21 16:42 from dpinto (3)

You're right, of course.

But if you wanted to sort on, say, the j-th element then use:

L:=sort(L,(a,b)->evalb(a[j]<b[j]));

If you wanted to sort on multiple elements, then you repeat the command for each element in reverse order of priority, e.g.
L:=sort(L,(a,b)->evalb(a[2]<b[2]));
L:=sort(L,(a,b)->evalb(a[1]<b[1]));

I suppose that would fail if the lists have different lengths. In any event, using a custom Boolean operator within the sort function seems to me to be the easiest approach for any number of sorting situations.

follow-up

Comment on 2008-03-21 17:03 from Joe Riel ( Maple Rating 4

1258)

Using a custom boolean operator is, as you say, the easiest approach. However, it isn't necessarily the fastest or more efficient technique. For many applications than may not matter. If speed is important, you might look at an earlier blog entry that was motivated by John's post.

Ordering a list of lists

Comment viewing options