Unsort: запоминание перестановки и отмена ее

Question

Предположим, у меня есть функция f, которая берет вектор v и возвращает новый вектор с элементами, преобразованными каким-либо образом. Это делается путем вызова функции g, которая предполагает, что вектор отсортирован. Поэтому я хочу, чтобы f было определено так:

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 *)
]

Какой лучший способ сделать "Unsort"?

Или мы могли бы по-настоящему придумать и заставить это как-то работать:

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

ДОБАВЛЕНО: Давайте сделаем этот бетон на игрушечном примере. Предположим, нам нужна функция f, которая берет вектор и преобразует его, добавляя к каждому элементу следующий наименьший элемент, если таковой имеется. Это легко написать, если предположить, что вектор отсортирован, поэтому давайте напишем вспомогательную функцию g, которая делает это предположение:

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

Теперь для функции, которую мы действительно хотим, f, которая работает независимо от того, отсортирована ли v:

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

Answer 1

Один из возможных методов:

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

дает

{г [с], г 1 , г [а], г [б], г [2], g [4], g [h], g [[Pi]]}

То есть

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

Изначально я узнал об этом из MathGroup, [EDITED]из поста Андрея Козловского

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

Answer 2

Вот образец "сортировочной упаковки" , предложенный Майклом Пилатом ранее

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}]

Answer 3

Благодаря TomD и Ярославу, вот, пожалуй, самый лаконичный / элегантный способ сделать это:

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

А благодаря Янусу, возможно, более эффективный способ:

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

Обратите внимание, что он делает 2 сортировки вместо 3.

Для потомков, вот моя первоначальная попытка, хотя я не думаю, что есть что-то, что можно было бы рекомендовать по сравнению с вышеупомянутым:Чтобы обратиться к Велисарию в комментариях, причина, по которой я не передаю g в качестве параметра, заключается в том, что я думаю о g как вспомогательной функции для f.Как будто у меня есть функция f, которую было бы легче написать, если бы я мог предположить, что ее аргумент был отсортированным вектором.Поэтому я пишу версию, которая предполагает это, а затем выполняю этот трюк с оберткой.