haskell - *O(n)* "forward"Data.Vector `permute` 函数

Question

Data.Vector API 提供了一个高效的 backpermute 函数，它基本上应用了索引映射 σ -向量到向量v ，即 v'[j] = v[σ[j]] .

或以列表语法表示(为简单起见):

backpermute :: [Int] -> [a] -> [a]
backpermute σ v = map (v !!) σ

如果 !! 则可能具有 O(n) 复杂度具有 O(1) 复杂度(我假设 Data.Vector )。现在我想要逆“正向” permute操作(或用于反转 σ -vector 本身的函数)，即类似(再次在列表语法中):

permute :: [Int] -> [a] -> [a]
permute σ = map snd . sortBy (comparing fst) . zip σ

invperm :: [Int] -> [Int]
invperm σ = permute σ [0..]

唉，由于 sortBy，上面的代码不是 O(n) .但是自从 σ假定为前缀 [0..] 的排列 permute应该可以用 Data.Vector 表示为 O(n) 算法API。

那么，如何实现高效的 O(n) permute (或者一个 O(n) invperm )根据 Data.Vector.*蜜蜂？

Answer 1

一元初始化，也许？

invSigma :: Vector Int -> Vector Int
invSigma s = create $ 
             do v <- new n
                zipWithM_ (write v) s (enumFromN 0 n)
                return v
  where n = V.length s