Menu Close

Agrupación por orden de aparición

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. 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. 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. antlopgom2
    agrupacion :: Eq a => [a] -> [a]
    agrupacion []     = []
    agrupacion [x]    = [x]
    agrupacion (x:xs) = filter (==x) (x:xs) ++ agrupacion (filter (/=x) (x:xs))
  4. 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. 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. 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. 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. 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.