取消排序:记住排列并撤消它 [英] Unsort: remembering a permutation and undoing it

问题描述

假设我有一个函数f，它接受向量v并返回一个新的向量，该向量具有以某种方式转换的元素. 通过调用假定向量已排序的函数g来做到这一点. 所以我想像这样定义f:

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

添加:让我们通过一个玩具示例来具体说明. 假设我们想要一个函数f，该函数采用一个向量并通过向每个元素添加下一个最小元素(如果有)来对其进行转换. 如果我们假设向量已排序，这很容易编写，因此让我们编写一个辅助函数g来进行此假设:

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]

现在对于我们真正想要的函数f而言，无论v是否排序，该函数都可以工作:

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

推荐答案

感谢TomD和Yaroslav，这可能是最简洁/优雅的方法:

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

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

感谢Janus，这是一种可能更有效的方法:

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

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

请注意，它执行2种排序，而不是3种.

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

为了解决注释中的belisarius，之所以没有将g作为参数传递，是因为我认为g是f的辅助函数. 就像我有一个函数f，如果我可以假设它的参数是一个有序的向量，它会更容易编写. 因此，我编写了一个假定该版本的版本，然后执行此包装技巧.

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.

这篇关于取消排序:记住排列并撤消它的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！