Unsort: remembering a permutation and undoing it

问题:

Suppose I have a function f that takes a vector v and returns a new vector with the elements transformed in some way. It does that by calling function g that assumes the vector is sorted. So I want f to be defined like so:

f[v_] := Module[{s, r},
  s = Sort[v];  (* remember the permutation applied in order to sort v *)
  r = g[s];
  Unsort[r]     (* apply the inverse of that permutation *)
]

What's the best way to do the "Unsort"?

Or could we get really fancy and have this somehow work:

answer = Unsort[g[Sort[v]]];

ADDED: Let's make this concrete with a toy example. Suppose we want a function f that takes a vector and transforms it by adding to each element the next smallest element, if any. That's easy to write if we assume the vector is sorted, so let's write a helper function g that makes that assumption:

g[v_] := v + Prepend[Most@v, 0]

Now for the function we really want, f, that works whether or not v is sorted:

f[v_] := (* remember the order; 
            sort it;
            call g on it;
            put it back in the original order;
            return it
         *)

回答1:

One possible method:

 mylist = {c, 1, a, b, 2, 4, h, \[Pi]}
    g /@ (Sort@mylist)[[Ordering@Ordering@mylist]]

gives

{g[c], g1, g[a], g[b], g[2], g[4], g[h], g[[Pi]]}

That is,

(Sort@mylist)[[Ordering@Ordering@mylist]] == mylist

I originally learned of the above from MathGroup, [EDITED] from a post by Andrzej Kozlowski

http://forums.wolfram.com/mathgroup/archive/2007/Jun/msg00920.html

回答2:

Here's a "sorting wrapper" pattern suggested by Michael Pilat earlier

Clear[g];
g[a_] := If[OrderedQ[a], a^2, Print["Failed"]];
g[{3, 2, 1}]
g[a_] := g[Sort@a][[Ordering@Ordering@a]] /; Not[OrderedQ[a]];
g[{3, 2, 1}]

回答3:

Thanks to TomD and Yaroslav, here's probably the most concise/elegant way to do it:

f[v_] := g[Sort@v][[Ordering@Ordering@v]]

And thanks to Janus, here's a perhaps more efficient way:

f[v_] := With[{o = Ordering@v}, g[v[[o]]][[Ordering@o]]]

Note that it does 2 sorts instead of 3.

For posterity, here's my original attempt, though I don't think it has anything to recommend it over the above:

f[v_] := With[{o = Ordering[v]}, Sort[Transpose[{o,g[v[[o]]]}]][[All,-1]]]

To address belisarius in the comments, the reason I'm not passing g as a parameter is because I'm thinking of g as a helper function for f. It's like I have a function f that would be easier to write if I could assume its argument was a sorted vector. So I write the version that assumes that and then do this wrapper trick.