仅使用列表反转线性时间的排列 [英] Invert a permutation in linear time, using only lists

问题描述

我想定义一个函数

invert :: [Int] -> [Int]

假定其输入是[0..(n-1)]的排列，并返回其反值.可以只使用列表和元组(不包含数组)来定义它，以使其在线性时间内运行吗?

that assumes that its input is a permutation of [0..(n-1)], and returns its inverse. Can one define it using only lists and tuples (without arrays) so that it runs in linear time?

这主要是出于学术兴趣；在实际代码中，我可能会使用Array或STArray或类似的代码.

This is primarily out of academic interest; in real code I might use Array or STArray or similar.

推荐答案

因此，这不使用仅列表".但这看起来非常合适.

So, this doesn't use "only lists". But it seemed to fit so well.

import qualified Data.Vector as V

invert :: [Int] -> [Int]
invert list = V.toList $ vec V.// assocs
  where vec = V.fromList list -- better ideas for initializing vec?
        assocs = zip (map pred list) [1..]

请参见矢量包 ，它声称//是 O(n).嗯，它说是 O(n + m)，但在这种情况下是n = m.

See the Vector package, which claims that // is O(n). Well, it says O(n+m), but in this case, n = m.

我将其加载到ghci中，得到与德米特里相同的答案. :)

I loaded it up into ghci and got the same answer as dmitry. :)

这篇关于仅使用列表反转线性时间的排列的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！