Invert swap to linear time using lists only

Question

I want to define a function

invert :: [Int] -> [Int] 

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

This is primarily an academic interest; in real code, I could use Array or STArray or similar.

Answer 1

Not sure about linear time, newbie.

 λ> (\x -> map snd $ sort $ zip x [1..(length x)]) [3,8,5,10,9,4,6,1,7,2] [8,10,1,6,3,7,9,2,5,4] 

Answer 2

Thus, it does not use "lists only". But it looked like it was so good.

 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..] 

See the Vector package for a statement that // is O (n). Well, that says O (n + m), but in this case n = m .

I downloaded it in ghci and got the same answer as dmitry. :)

Answer 3

It seems to me that you cannot do this in linear time. To implement O (n) with time complexity, you will need to create a list of results out of order, which you cannot do directly with cons-lists, I suppose.

Answer 4

Since there seems to be no positive answer to the actual question, I will add my cheat to the list of non-solutions:

 invert :: [Int] -> [Int] invert lst = take lng $ map (fromIntegral.(`mod`h)) $ iterate (`div`h) $ sum $ zipWith (\k x->k*h^x) [0..] lst where h::Integer h = fromIntegral lng lng = length lst 

Answer 5

If permutations are represented as lists of disjoint cycles, then

 invert :: [[Int]] -> [[Int]] invert = map reverse 

works in linear time. I'm not sure if there is a linear way to convert back and forth between different views.