19
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\begingroup$ Yes you can. Have a look at Ordering function. $\endgroup$ Commented Feb 8, 2013 at 11:01
  • $\begingroup$ @LeonidShifrin How can I make the "Ordering" function work for a SortBy function where we sort by column 1, then 2, etc.? $\endgroup$ Commented Feb 8, 2013 at 11:23
  • 1
    $\begingroup$ You most certainly can do this, just the ordering function would become more complex,and this can possibly degrade the efficiency. Another option is to construct a list with positions like Transpose[{lst,Range[Length[lst]]}],where lst is the original list, and use SortBy on this one, changing all your sorting functions as f-> First@f[#]&. Then, after a list is sorted, extract positions of elements of the original list in a sorted list as sorted[[All,2]]. $\endgroup$ Commented Feb 8, 2013 at 11:29

4 Answers 4

Reset to default
14
$\begingroup$

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.

Improve this answer
$\endgroup$
12
$\begingroup$

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
Improve this answer
$\endgroup$
1
  • $\begingroup$ +1. This is nice. I was surprised that Szabolcs's solution was so fast, and here is another nice application of it. $\endgroup$ Commented Mar 16, 2013 at 2:44
2
$\begingroup$

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"}
Improve this answer
$\endgroup$
5
  • 1
    $\begingroup$ Istvan, the way you compute order is really not efficient. Efficent way would be Ordering[Ordering[ref]], and that's all there is to it here, really (so you don't need your longer code using rules either) . $\endgroup$ Commented Feb 8, 2013 at 12:36
  • $\begingroup$ @Leonid Well, I hoped you will make it yourself an answer :) Efficiency is definitely not my table, and my mind halts before entering a recursive loop (second Ordering)... Thanks anyway, edited in. $\endgroup$ Commented Feb 8, 2013 at 13:19
  • 1
    $\begingroup$ If I wanted to make this a separate answer, I would have done so at the start :). I think it would be better to start with order = Ordering@Ordering@ref, replacing the slower Position- based code, since people tend to pay more attention to things at the begining of the post. But this is up to you, of course. $\endgroup$ Commented Feb 8, 2013 at 13:26
  • $\begingroup$ @Leonid It felt like stealing your line. Now moved up for better understanding. $\endgroup$ Commented Feb 8, 2013 at 19:19
  • 1
    $\begingroup$ Well, I left that comment specifically for you to use it should you wish to do so. I posted another answer because it became clear that the OP wants SortBy-like behavior with a list of comparison functions, and it was more than just using Ordering. $\endgroup$ Commented Feb 8, 2013 at 19:32
1
$\begingroup$

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}

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.