*O(n)*“向前”Data.Vector ` `permute`‘函数

Question

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

或用列表语法表示(为了简单起见)：

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

如果!!具有O(1)复杂度(我假设为Data.Vector)，那么它可以具有O(n)复杂度。现在，我需要逆的“转发”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 API表示为O(n)算法。

那么，如何根据permute API实现一个有效的O(n) invperm(或者O(n) invperm)？

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

Answer 2

因此，permute应该取一个指数向量和一个值向量，并生成一个新的向量，以便将每个值存储在相应的索引处，即v'[σ[j]] = v[j]，即backpermute的逆值。

据我所知，Data.Vector中没有用索引值对构建新Vector的函数，但是有一个更新现有向量的函数，即update :: Vector a -> Vector (Int, a) -> Vector a。它的运行时是O(m+n)，其中m是向量的大小，n是更新的次数。

还有一个变体update_ :: Vector a -> Vector Int -> Vector a -> Vector a，它接受两个向量而不是成对的向量。太完美了。现在我们只需要一个初始向量来用这些值“覆盖”。假设σ是一个有效的排列，那么所有的项都会被更新，所以任何与v相同类型和长度的向量都会被更新，所以我们可以重用v。

permute :: Vector Int -> Vector a -> Vector a
permute σ v = update_ v σ v

由于σ的长度与v相同，所以运行时为O(n)。

一个比较安全的选择是使用底部值的向量。这样，如果您试图读取σ中没有索引的项，而不是默默地获取错误的结果，您将得到一个错误。

permute σ v = update_ (replicate (length v) undefined) σ v