Haskell: invertir una permutación en el tiempo lineal, utilizando solo lista

Question

quiero definir una función

invert :: [Int] -> [Int] 

que asume que su entrada es una permutación de [0..(n-1)], y devuelve su inversa. ¿Se puede definir utilizando solo listas y tuplas (sin matrices) para que se ejecute en tiempo lineal?

Esto es principalmente por interés académico; en código real podría usar Array o STArray o similar.

Answer 1

No estoy seguro sobre el tiempo lineal, solo una nota para principiantes.

λ> (\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

Me parece que no se puede hacer esto en tiempo lineal. Para una implementación con una complejidad de tiempo O (n) necesitará crear la lista de resultados fuera de servicio, lo que no se puede hacer directamente con cons-lists, supongo.

Answer 3

Por lo tanto, esto no utiliza "solo listas". Pero parecía encajar tan bien.

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

Ver the Vector package, que afirma que // es O (n). Bueno, dice O (n + m), pero en este caso, n = m.

Lo cargué en ghci y obtuve la misma respuesta que dmitry. :)

Answer 4

Si las permutaciones se representan como listas de ciclos disjuntos, entonces

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

carreras en tiempo lineal. No estoy seguro si hay una forma lineal de convertir entre las diferentes representaciones.

Answer 5

Como no parece ser una respuesta positiva a la pregunta real, voy a añadir mi tramposo a la lista de los no-soluciones:

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