# Comparing two lists lexically

I have two lists of integers a and b of equal length, and I would like to define a>b as follows: let i be the smallest index such that a[[i]]>b[[i]] (if there is one), and j the smallest integer such that a[[j]]<b[[j]]. Then a>b if i>j. In other words, marching left to right across both lists, the first is greater than the second if the first position you encounter where the two lists are unequal has a greater value in a than in b.

So for example {1,2,1} > {1,1,4} since the lists first differ in position 2, and there the first is greater than the second.

I know how to do this using a loop, but that seems remarkably inappropriate.

Another method is by comparing Position[Map[# > 0 &, a-b], True, 1] and Position[Map[# < 0 &, a-b], True, 1], or Position[Thread[Greater[a,b]],True,1] and Position[Thread[Less[a,b]],True,1]. But both of these fail without additional code in the case where one or the other returns an empty list. Is there a cleaner way?

## 3 Answers

Here are a couple of possibilities.

inOrder1[a_List, a_] := 0
inOrder1[a_List, b_List] /; MatrixQ[{a, b}, IntegerQ] :=
Sign[First[a - b /. 0 -> Sequence[]]]

In[8]:= inOrder1[{1, 2, 1}, {1, 4, 0}]

(* Out[8]= -1 *)

inOrder2[a_List, b_List] /; MatrixQ[{a, b}, IntegerQ] := Catch[
Module[{sg},
Scan[If[(sg = Sign[#[[1]] - #[[2]]]) != 0, Throw[sg]] &,
Transpose[{a, b}]]; 0]]

In[11]:= inOrder2[{1, 6, 1}, {1, 4, 0}]

(* Out[11]= 1 *)


These can be translated to True/False results if one wants to put them into Sort as an ordering predicate optional argument.

Another possibility is to just use Sort and hope it does what you want. (It might but then again even if it does, the internals could change in future.)

I don't know if this is clearer, but as Sort using "lexical" ordering on same-length List comparison, I would transfer the original Lists into same length ones, then invoke Sort on them:

Clear[lexicallySort]
lexicallySort[lst : {{_?NumericQ ..} ..}] := lst //
Sort@PadRight[#,{Length@#,Max[Length/@#]},Min[#]-1]/.Evaluate[Min[#]-1]:>Sequence[] &

lexicallySort[{
{1, 2, 1, 3, 1, 3, 1, 3},
{1, 2, 1, 3, 1, 1, 1, 4},
{1, 2, 1, 3},
{1, 2, 1, 3, 1, 1},
{1, 2, 1, 3, 1, 3, 1, 4},
{1, 2, 1, 3, 1, 3},
{1, 2, 1, 3, 1, 1, 1, 3},
{1, 2},
{1, 3}
}] // Grid

1 2
1 2 1 3
1 2 1 3 1 1
1 2 1 3 1 1 1 3
1 2 1 3 1 1 1 4
1 2 1 3 1 3
1 2 1 3 1 3 1 3
1 2 1 3 1 3 1 4
1 3


Never mind, I see the answer. I didn't realize that Sort on lists uses exactly [the inverse of] the sorting I want. So !OrderedQ[a,b]returns True exactly when a>b.