Menu Close

Agrupación por orden de aparición

José A. Alonso,

Definir la función

   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"

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)
Medio
, , , , ,

8 soluciones de “Agrupación por orden de aparición”

  1. Responder
    cescarde 
    agrupacion :: Eq a => [a] -> [a]
agrupacion []  = []
agrupacion [x] = [x] 
agrupacion (x:xs) | elem x xs = filter (==x) (x:xs) ++ agrupacion zs
                  | otherwise = x : agrupacion zs
  where zs = filter (/=x) xs
  2. Responder
    albcercid 
    agrupacion :: Eq a => [a] -> [a]
agrupacion xs = aAux [] xs
  where aAux v [] = []
        aAux v (x:xs) | elem x v  = aAux v xs
                      | otherwise = reps x xs ++ aAux (x:v) xs
        reps x xs = x : [ x | a <- xs, a == x]
  3. Responder
    antlopgom2 
    agrupacion :: Eq a => [a] -> [a]
agrupacion []     = []
agrupacion [x]    = [x]
agrupacion (x:xs) = filter (==x) (x:xs) ++ agrupacion (filter (/=x) (x:xs))
  4. Responder
    josejuan 
    -- Coste O(n^2) dado que sólo tenemos `Eq`
agrupacion xs = concat [filter (x==) xs | x <- nub xs]
 
 
 
-- Si tenemos `Ord` podemos hacerlo en `O(n log n)`
agrupación :: Ord a =>[a] ->[a]
agrupación = concatMap snd
           . sort
           . map (xs@((_,i):_) ->(i, map fst xs))
           . groupBy ((==) `on` fst)
           . sort
           . flip zip [0..]
  5. Responder
    enrnarbej 
    agrupacion :: (Ord a, Eq a) => [a] -> [a]
agrupacion xs =
  concat $ map (x -> head (filter (all (== x)) grupos)) orden
  where
    orden  = nub xs
    grupos = group $ sort xs
  6. Responder
    Antonio Morales (antmorper3) 
    import Data.List
 
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) =
  [a | a <- (x:xs), a == x] ++ agrupacion (xs \ intersect xs [x])
  7. Responder
    Chema Cortés 
    import Data.List (partition)
 
agrupacion :: Eq a => [a] -> [a]
agrupacion []     = []
agrupacion (x:xs) = x : ys ++ agrupacion zs
  where (ys,zs) = partition (==x) xs
  8. Responder
    Juanjo Ortega (juaorture) 
    import Data.List 
 
agrupacion :: Eq a => [a] -> [a]
agrupacion [] = []
agrupacion (x:xs) = x : eq ++ agrupacion (xs \ eq)
  where eq = [a | a <- xs, a == x]

Escribe tu solución

Este sitio usa Akismet para reducir el spam. Aprende cómo se procesan los datos de tus comentarios.