Unsort: запомнить перестановку и уничтожить ее

Question

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

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[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

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

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

и благодаря Януса, вот, возможно, более effic диентом путь:

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

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

для потомства, вот моя оригинальная попытка, хотя я не думаю, что это не имеет ничего, чтобы рекомендовать его на выше:

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

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

Answer 2

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

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

дает

{г [с], г 1, г [а], г [Ь], г [2], г [4], г [ч], г [[Р]]}

То есть,

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

первоначально я узнал выше от MathGroup, [Изменено] с поста Анджея Kozlowsk I

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

Answer 3

Вот "сортировка обертка" модель suggested Майкл Pilat ранее

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