15
$\begingroup$

I was surprised to discover that Mathematica does not sort lists-of-lists (LLs) lexicographically by default. For example, applying Sort to {{1, 2}, {3}}, which is already lexicographically ordered, destroys this order, producing {{3}, {1, 2}}.

Is there a standard Mathematica function, or idiom, for lexicographically ordering a LL?

EDIT: If I were to roll my own, I'd implement a lexicographic comparator function, to be passed as the second argument to Sort:

cmpLLs[_][{}, b_List] := True;
cmpLLs[_][a_List, {}] := False;
cmpLLs[by_][a_List, b_List] :=
  Module[{va = by[First[a]], vb = by[First[b]]},
    If[va == vb, cmpLLs[Rest[a], Rest[b]], va < vb]
  ];
cmpLLs[a_List, b_List] := cmpLLs[Identity][a, b];

(* test borrowed from Leonid Shifrin's answer *)
test = {{3}, {7}, {4, 6, 2}, {7, 7, 6}, {10, 3, 9}, {6, 7, 9}, {1, 7, 7}};

Sort[test, cmpLLs]
(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)

Sort[test, cmpLLs[Plus]]  (* just for giggles *)
(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)

Sort[test, cmpLLs[Minus]]
(* {{10, 3, 9}, {7}, {7, 7, 6}, {6, 7, 9}, {4, 6, 2}, {3}, {1, 7, 7}} *)

Not a stack-friendly implementation, I admit...

$\endgroup$
  • 3
    $\begingroup$ You could resort to ToString before ordering: ToExpression /@ Sort[ToString /@ {{3}, {1, 2}}] (or roll your own ordering function). $\endgroup$ – Yves Klett Jun 10 '15 at 13:39
  • 4
    $\begingroup$ This is due to Sort on lists sorting by the size of the sub-list first, and only applying lexicographic sort for equal-size lists. This is in fact documented. $\endgroup$ – Leonid Shifrin Jun 10 '15 at 16:18
  • 2
    $\begingroup$ Glad I could help. Re: docs - have a look at the notes in documentation of Sort, under details, fourth bullet point: " usually orders expressions by putting shorter ones first, and then comparing parts in a depth-first manner. ". $\endgroup$ – Leonid Shifrin Jun 10 '15 at 16:56
  • 1
    $\begingroup$ @BlacKow The problem with kjo's implementation is that Mathematica Lists are arrays, not linked lists. So, apart from the issues related to tail calls, there is also the issue related to list copying on every recursive step. The proper way to do this sort of things in Mathematica would be to use linked lists. $\endgroup$ – Leonid Shifrin Jun 11 '15 at 2:15
  • 2
    $\begingroup$ The reason to sort on length first is that it is often a quick discriminator, hence Ordering is less likely to be slow e.g. from deep recursion in a depth first search. $\endgroup$ – Daniel Lichtblau Jun 11 '15 at 20:56
12
$\begingroup$

This is due to Sort on lists sorting by the size of the sub-list first, and only applying lexicographic sort for equal-size lists. This is in fact documented.

Based on this observation, here is one possibility:

ClearAll[lexicographicListSort]
lexicographicListSort[lst_List] :=
  Module[{lengths = Length /@ lst, ord},
    ord = Ordering @ PadRight[lst, {Length[lst], Max[lengths]}];
    MapThread[Take, {lst[[ord]], lengths[[ord]]}]
  ]

For example:

test = {{3}, {7}, {4, 6, 2}, {7, 7, 6}, {10, 3, 9}, {6, 7, 9}, {1, 7, 7}}

lexicographicListSort[test]

(* {{1, 7, 7}, {3}, {4, 6, 2}, {6, 7, 9}, {7}, {7, 7, 6}, {10, 3, 9}} *)

EDIT

As BlacKow rightly noted, the above code can be very memory-inefficient, in cases when some of the sublists are really large. The simplest naive solution to trade speed for memory is to make such padding local to the comparison event:

sortlNaive[l_List] :=
  Sort[
    l, 
    With[{max = Max[Length[#1], Length[#2]]}, 
      OrderedQ[PadRight[#, max] & /@ {##}]
    ] &
  ]

However, this method is pretty inefficient. The reason is that we are leaving the "optimal code" Mathematica's paradigm to work with lots of data at once (it is possible to explain this particular case in more detail).

Saving explanations and benchmarks for some near future (when I get more time), here is a version which generally performs better or much better than sortlNaive, while being much more memory-efficient than lexicographicListSort (V10+, since I use operator forms, but can be easily rewritten to be used in earlier versions):

ClearAll[sortl];
sortl[{}, _ : None] := {};
sortl[{x_}, _ : None] := {x};
sortl[l_List] := sortl[l, 1];
sortl[l_List, lev_] :=
  With[{min = Min[Length /@ l]},
    Composition[
      Flatten[#, 1] &,
      Map[
        If[Length[#] == 1,
          #,
          With[{smallest = LengthWhile[#, Length[#] == lev &]},
            Take[#, smallest]~Join~sortl[Drop[#, smallest], lev + 1]
          ]
        ] &
      ],
      SplitBy[#, Take[#, {lev, min}] &] &,
      SortBy[Take[#, {lev, min}] &]
    ]@l
  ]

A question of automation of the choice between lexicographicListSort and sortl is an interesting one, but requires more time than I currently have, to do it justice.

| improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ What if the average length of your sub-list is 5, but the largest sub-list has million elements? Your padding will be wasting lots of memory, right? $\endgroup$ – BlacKow Jun 10 '15 at 17:20
  • $\begingroup$ @BlacKow Yes, you are right, that's a good point! I added some code to address that issue. $\endgroup$ – Leonid Shifrin Jun 11 '15 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.