Retaining and reusing a one-to-one mapping from a sort

Ok, here is my stab at it. As I mentioned in comments, I can see two ways to solve this.

Ordering - based solution (and a by-product: compilable SortBy)

One way is to use Ordering, but the problem here is that SortBy when used with a list of functions performs in a way where each function serves as a tie-breaker for ties resulting from application of a previous function to a pair of list elements. Should we have a built-in OrderingBy function, and that would be easy. But Ordering requires a single sorting function, just like Sort.

Generating a comparison function

The solution I will use here is to generate a possibly complex single comparison function from a list of functions used in SortBy. Here is a possible code for it:

Clear[generateSortingFunction];
generateSortingFunction[funcs__] :=
   Module[{sortFGenerator},
     sortFGenerator[funcs] //. {
        sortFGenerator[f_, funs___] :> 
           (With[{fst = f[#1], sec  = f[#2]},
               If[OrderedQ[{fst, sec}],
                  If[OrderedQ[{sec, fst}],
                     sortFGenerator[funs][##],
                     True
                  ],
                  False
               ]] &),
        sortFGenerator[][__] :> True}
   ];

Assuming that a list of functions in your example is {#[[1]]&,#[[2]]&}, we will have then:

sf = generateSortingFunction[#[[1]]&,#[[2]]&]

With[{fst$=(#1[[1]]&)[#1],sec$=(#1[[1]]&) [#2]},
   If[OrderedQ[{fst$,sec$}],
     If[OrderedQ[{sec$,fst$}],
        (With[{fst$=(#1[[2]]&)[#1],sec$=(#1[[2]]&)[#2]},
            If[OrderedQ[{fst$,sec$}],
               If[OrderedQ[{sec$,fst$}],True,True],
               False]
            ]&)[##1],
        True],
     False]]&

This is admittedly a mess, but the reason I decided to go with the code generation is that such generated pure functions can be compiled, which in this case can be checked by executing e.g.

cf = 
   Compile[{{fst, _Integer, 1}, {sec, _Integer, 1}},
      sf[fst, sec], 
      CompilationOptions -> {"InlineExternalDefinitions" -> True}
   ]

To some extent, this works around SortBy not being compilable, since Sort with this comparison function can be compiled and effectively would work as SortBy.

Implementing orderingBy

With the above construct, we can now implement our own version of orderingBy, as follows:

ClearAll[orderingBy];
orderingBy[lst_, funs_List] :=
   Ordering[lst, All, generateSortingFunction[funs]];

Now, for your example, we have:

orderingBy[data,{#[[1]]&,#[[2]]&}]

(* {6,1,2,3,4,5} *)

Using SortBy

The second option is to use SortBy itself, but on a more complex list where positions will be added to elements. I will use here the code from this answer, which allows to elegantly compose functions passed to SortBy. I will reproduce this here for completeness:

ClearAll[sortFun];
sortFun /: SortBy[expr_, sortFun[funs_List, partFun_]] := 
   SortBy[expr, Map[Composition[#, partFun] &, funs]];

with this, the implementation ot orderingBy function is straight-forward: "dress" original list with element positions, reorder it by SortBy, and extract positions from reordered list:

ClearAll[orderingByAlt]
orderingByAlt[lst_, funs_List] :=
   SortBy[
       Transpose[{#, Range[Length[#]]}] &@lst, 
       sortFun[funs, First]
   ][[All, 2]]

which of course gives the same result:

orderingByAlt[data, {#[[1]] &, #[[2]] &}]

(* {6, 1, 2, 3, 4, 5}  *)

Remarks

Which of the two approaches to pick is largely a matter of taste. The second one seems more economical, since we reused higher-level abstraction (SortBy). However, if for example one would want to compile the code, then the first approach seems preferable, since it generates compilable code.


Using Szabolcs's clever inversion method we can write a more concise and efficient form than the standard decorate-and-sort:

orderingBy[lst_, sfuns_List] :=
  SortBy[
    Range @ Length @ lst,
    Cases[sfuns, f_ :> (f @ lst[[#]] &)]
  ]

Update: additional definitions to handle default tie-break and provide an operator form:

orderingBy[lst_, sfn_] := orderingBy[lst, {sfn, Identity}]

orderingBy[fns_][lst_] := orderingBy[lst, fns]

Now:

data = {{4, 5}, {6, 1}, {11, 87}, {24, 52}, {90, 4}, {4, 4}};

orderingBy[data, {#[[1]] &, #[[2]] &}]

 {6, 1, 2, 3, 4, 5}

This proves to be an order of magnitude faster than Leonid's orderingByAlt:

data = RandomInteger[10000, {500000, 2}];

orderingByAlt[data, {#[[1]] &, #[[2]] &}] // Timing // First (* Leonid's function *)

orderingBy[data, {#[[1]] &, #[[2]] &}]    // Timing // First (* my function *)

2.0444

0.226

Tags:

Sorting

Recent Posts