Definir la función
agrupacion :: Eq a => [a] -> [a] |
agrupacion :: Eq a => [a] -> [a]
tal que (agrupacion xs) es la lista obtenida agrupando los elementos de xs según su primera aparición. Por ejemplo,
agrupacion [3,1,5,1,7,1,5,3] == [3,3,1,1,1,5,5,7]
agrupacion "babcacb" == "bbbaacc" |
agrupacion [3,1,5,1,7,1,5,3] == [3,3,1,1,1,5,5,7]
agrupacion "babcacb" == "bbbaacc"
Soluciones
import Data.List (nub, partition)
-- 1ª definición
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) =
x : filter (==x) xs ++ agrupacion (filter (/=x) xs)
-- 2ª definición
agrupacion2 :: Eq a => [a] -> [a]
agrupacion2 xs = concat [filter (x==) xs | x <- nub xs]
-- 3ª definición
agrupacion3 :: Eq a => [a] -> [a]
agrupacion3 [] = []
agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs
where (ys,zs) = partition (==x) xs
-- Comparación de eficiencia
-- λ> import Data.List (cycle)
-- λ> :set +s
-- λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (24.40 secs, 3,173,123,368 bytes)
-- λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (13.71 secs, 2,333,129,416 bytes)
-- λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (22.33 secs, 5,080,127,944 bytes) |
import Data.List (nub, partition)
-- 1ª definición
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) =
x : filter (==x) xs ++ agrupacion (filter (/=x) xs)
-- 2ª definición
agrupacion2 :: Eq a => [a] -> [a]
agrupacion2 xs = concat [filter (x==) xs | x <- nub xs]
-- 3ª definición
agrupacion3 :: Eq a => [a] -> [a]
agrupacion3 [] = []
agrupacion3 (x:xs) = x : ys ++ agrupacion3 zs
where (ys,zs) = partition (==x) xs
-- Comparación de eficiencia
-- λ> import Data.List (cycle)
-- λ> :set +s
-- λ> sum (agrupacion (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (24.40 secs, 3,173,123,368 bytes)
-- λ> sum (agrupacion2 (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (13.71 secs, 2,333,129,416 bytes)
-- λ> sum (agrupacion3 (take (10^7) (cycle [0,1,2,3])))
-- 15000000
-- (22.33 secs, 5,080,127,944 bytes)
Se puede imprimir o compartir con
8 soluciones de “Agrupación por orden de aparición”