Generating inverse permutation

问题:

Suppose we are given a vector foo and we have to temporarily permute it (sort or re-order it), compute some vector bar on the base of it, and finally permute back both foo and bar to the original order of foo - that means inverse permutation:

foo <- c(1, 7, 3, 5, 2)
o <- order(foo)
foo <- foo[o] # Now foo is permuted, and sorted: foo == 1 2 3 5 7
bar = 2 * foo # bar == 2 4 6 10 14

And here should go your answer, such that we have the below desired final values:

foo == 1 7 3 5 2
bar == 2 14 6 10 4

How to do this?

Please simply do not reply: "you could do bar = 2 * foo and not permute it". This is just a simple example. In some situations we have to sort foo for efficiency (quick search over it) or something like that.

回答1:

This will work, because [order(o)] inverts the action of [o]:

foo <- c(1, 7, 3, 5, 2)
o <- order(foo)

(foo[o]*2)[order(o)]
# [1]  2 14  6 10  4

To show that it works more generally:

testAlgorithm <- function(foo) {
    o <- order(foo)
    identical(foo, foo[o][order(o)])
}

x <- c(1, 7, 3, 5, 2)
y <- c(1,2,5,7,4, 99, 88, 3, 0)
z <- sample(1000)                  ## (No ties)
zz <- sample(1000, replace=TRUE)   ## (Many ties)
all(sapply(list(x,y,z,zz), testAlgorithm))
[1] TRUE

回答2:

To recover the original order, use order(o):

> (foo[o]*2)[order(o)]
[1]  2 14  6 10  4