Ordenación por frecuencia

PorJosé A. Alonso 11-enero-201819-febrero-2018

Definir la función

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

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

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)

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 Comentarios

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)

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)

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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

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

Responder

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]

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]

Responder

import           Data.List (group, sortBy)
import           Data.Ord  (comparing)

ordPorFrecuencia :: Ord a => [a] -> [a]
ordPorFrecuencia = concat
                 . sortBy (flip (comparing length))
                 . group
                 . sortBy (flip compare)

import Data.List (group, sortBy)

import Data.Ord (comparing)

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

ordPorFrecuencia = concat

. sortBy (flip (comparing length))

. group

. sortBy (flip compare)

Responder

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico

Soluciones

Se puede imprimir o compartir con

8 Comentarios

Escribe tu soluciónCancel reply

Entradas recientes

Buscar

Correo electrónico