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.*
蜜蜂?
最佳答案
一元初始化,也许?
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
关于haskell - *O(n)* "forward"Data.Vector `permute` 函数,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/6731679/