Menu Close

Ordenación por frecuencia

Definir la función

   ordPorFrecuencia :: Ord a => [a] -> [a]

tal que (ordPorFrecuencia xs) es la lista obtenidas ordenando los elementos de xs por su frecuencia, de los que aparecen más a los que aparecen menos, y los que aparecen el mismo número de veces se ordenan de manera creciente según su valor. Por ejemplo,

   ordPorFrecuencia "canalDePanama"      ==  "aaaaannmlecPD"
   ordPorFrecuencia "11012018"           ==  "11110082"
   ordPorFrecuencia [2,3,5,3,7,9,5,3,7]  ==  [3,3,3,7,7,5,5,9,2]

Soluciones

import Test.QuickCheck
 
import Data.List (group, sort, sortBy)
import Data.Function (on)
 
-- 1ª solución
-- ===========
 
ordPorFrecuencia1 :: Ord a => [a] -> [a]
ordPorFrecuencia1 xs =
  concatMap snd (reverse (sort [(length xs,xs) | xs <- group (sort xs)]))
 
-- 2ª solución
-- ===========
 
ordPorFrecuencia2 :: Ord a => [a] -> [a]
ordPorFrecuencia2 =
    concat . reverse . sortBy comparaPorLongitud . group . sort
 
comparaPorLongitud :: [a] -> [a] -> Ordering
comparaPorLongitud xs ys = compare (length xs) (length ys)
 
-- 3ª solución
-- ===========
 
ordPorFrecuencia3 :: Ord a => [a] -> [a]
ordPorFrecuencia3 =
    concat . reverse . sortBy (compare `on` length). group . sort
 
-- Comparación de eficiencia
-- =========================
 
--    λ> xs = show (2^2000000)
--    λ> last (ordPorFrecuencia1 xs)
--    '8'
--    (1.45 secs, 938,345,320 bytes)
--    λ> last (ordPorFrecuencia2 xs)
--    '8'
--    (1.33 secs, 900,239,200 bytes)
--    λ> last (ordPorFrecuencia3 xs)
--    '8'
--    (1.30 secs, 900,241,848 bytes)

8 soluciones de “Ordenación por frecuencia

  1. jaiturrod
    import Data.List
     
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia xs = concat (sortBy comp(group (sort xs)))
      where comp ys zs = compare (length zs) (length ys)
  2. alerodrod5
    import Data.List
     
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia xs = concat (map snd (agrupada xs))
     
    agrupada xs =reverse(sort(zip(map length ys) ys))
      where ys = (group.sort) xs
  3. angruicam1
    import Data.List (sortOn,sort,groupBy)
     
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia xs =
      reverse
      . map fst
      . concatMap sort
      . groupBy agrupaSegundo
      . sortOn snd
      $ ys
      where ys = zip xs [length zs | x <- xs
                           , let zs = filter (== x) xs]
     
    agrupaSegundo :: Eq b -> (a,b) -> (a,b)
    agrupaSegundo (_,x) (_,y) = x == y
    • angruicam1
      import Data.List (group,sort)
      import Data.Map (fromListWith,toDescList)
       
      ordPorFrecuencia :: Ord a => [a] -> [a]
      ordPorFrecuencia xs = concatMap snd . toDescList . fromListWith (++) $ ys
        where ys = zip (map length zs) zs
              zs = group . sort $ xs
  4. pabhueacu
    import Data.List
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia = concat.sortBy(flip f).group.sort 
      where f l1@(h1:xs) l2@(h2:ys) | x > y = GT
                                    | x < y = LT
                                    | otherwise = compare h1 h2 
                                     where x = length l1
                                           y = length l2
  5. albcarcas1
     
    import Data.List
     
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia xs = concat[y | (x,y) <- zs]
      where zs = reverse(sort(zip (map length (group (sort xs))) (group (sort xs))))
  6. carriomon1
    import Data.List 
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia xs = reverse [ y | (x,y) <- sort $ listaFrecuencias xs] 
     
    frecuencias :: Eq a => a -> [a] -> (Int, a)
    frecuencias x xs | not (elem x xs) = error " x no pertenece a xs"
                     | otherwise = (length $ elemIndices x xs, x)
     
    listaFrecuencias xs = [frecuencias x xs | x <- xs]
  7. Chema Cortés
    import           Data.List (group, sortBy)
    import           Data.Ord  (comparing)
     
    ordPorFrecuencia :: Ord a => [a] -> [a]
    ordPorFrecuencia = concat
                     . sortBy (flip (comparing length))
                     . group
                     . sortBy (flip compare)

Leave a Reply

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