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

Question

Imagine I sort the elements of an array $Q$ by some means. Perhaps I sort strictly by the elements in the first column, perhaps I use SortBy[...] to sequentially sort by the elements in successive columns, etc. Here, regardless of what I do, the result of this sort will be some one-to-one mapping from items in $Q$ to some items in the sorted array, $Q^*$.

Can I somehow retain or reuse this particular one-to-one mapping function on some other array with the same dimensions as $Q$? Very specifically, I mean that if we move element $q_i \in Q$ at position $(a_1, a_2, ...)$ in $Q$ to some new position $(b_1, b_2, ...)$ in $Q^*$, then we corresponding move the same element $h_i \in H$ from $(a_1, a_2, ...)$ in $H$ to $(b_1, b_2, ...)$ in $H^*$. And we do this regardless of the identity of $h_i$, i.e. we're not repeating the sort.

---

To provide a specific example of where I'm getting in trouble, I'd like to sort the following list by the first column, then the second (with this priority):

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

 In[...]:= SortBy[data, {#[[1]], #[[2]]} &]
 Out[...]:= {{4, 4}, {4, 5}, {6, 1}, {11, 87}, {24, 52}, {90, 4}}

However:

  In[...]:= Ordering[SortBy[data, {#[[1]], #[[2]]} &]]
  Out[...]:= {1, 2, 3, 4, 5, 6} 

What I wanted from Ordering[...] was:

  Out[...]:= {6, 1, 2, 3, 4, 5}

How can I make the above work?

Answer 1

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.

Answer 2

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

Answer 3

Using Odering (assuming that ref and set are of same length):

set[[Ordering@Ordering@ref]]

or a more complicated, less efficient way is:

pos = Range@Length@set;
set[[pos /. Thread[Ordering@ref -> pos]]]

{"E", "A", "D", "C", "B"}

An even more complicated way:

ref = {"e", "a", "d", "c", "b"};
set = {"A", "B", "C", "D", "E"};

order = Position[Sort@ref, #, 1][[1, 1]] & /@ ref

{5, 1, 4, 3, 2}

set[[order]]

{"E", "A", "D", "C", "B"}

Answer 4

Since V 12.0 there is OrderingBy which simplifies the solution considerably:

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

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

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