Mayores que la mitad

PorJosé A. Alonso 12-diciembre-201619-diciembre-2016

Definir la función

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

1	mayoresMitad :: Ord a => [a] -> [a]

tal que (mayoresMitad xs) es la lista de los elementos de xs que son mayores que la mitad de los elementos de xs, suponiendo que los elementos de xs son distintos. Por ejemplo,

   sort (mayoresMitad [1,6,3,4])    ==  [4,6]
   sort (mayoresMitad [1,6,3,4,7])  ==  [4,6,7]
   sort (mayoresMitad [1,6,3,4,2])  ==  [3,4,6]
   length (mayoresMitad3 [1..10^6]) ==  500000

sort (mayoresMitad [1,6,3,4]) == [4,6]

sort (mayoresMitad [1,6,3,4,7]) == [4,6,7]

sort (mayoresMitad [1,6,3,4,2]) == [3,4,6]

length (mayoresMitad3 [1..10^6]) == 500000

Nota: Se considera que si la lista tiene 2n+1 elementos, su mitad tiene n elementos.

Soluciones

import Data.List (sort)

-- 1ª solución:
mayoresMitad1 :: Ord a => [a] -> [a]
mayoresMitad1 xs =
  [x | x <- xs
     , length (filter (<=x) xs) > k]
  where k = length xs `div` 2 

-- 2ª solución
mayoresMitad2 :: Ord a => [a] -> [a]
mayoresMitad2 xs = aux xs
  where aux [] = []
        aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys
                   | otherwise                        = aux ys
        k = length xs `div` 2 

-- 3ª solución
mayoresMitad3 :: Ord a => [a] -> [a]
mayoresMitad3 xs = drop k (sort xs)
  where k = length xs `div` 2 

-- Comprobación de eficiencia
--    λ> length (mayoresMitad1 [1..4*10^3])
--    2000
--    (3.79 secs, 442,631,712 bytes)
--    λ> length (mayoresMitad2 [1..4*10^3])
--    2000
--    (11.82 secs, 1,463,762,192 bytes)
--    λ> length (mayoresMitad3 [1..4*10^3])
--    2000
--    (0.02 secs, 0 bytes)

import Data.List (sort)

-- 1ª solución:

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

mayoresMitad1 xs =

[x | x <- xs

, length (filter (<=x) xs) > k]

where k = length xs `div` 2

-- 2ª solución

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

mayoresMitad2 xs = aux xs

where aux [] = []

aux (y:ys) | length [x | x <- xs, x <= y] > k = y : aux ys

| otherwise = aux ys

k = length xs `div` 2

-- 3ª solución

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

mayoresMitad3 xs = drop k (sort xs)

where k = length xs `div` 2

-- Comprobación de eficiencia

-- λ> length (mayoresMitad1 [1..4*10^3])

-- 2000

-- (3.79 secs, 442,631,712 bytes)

-- λ> length (mayoresMitad2 [1..4*10^3])

-- 2000

-- (11.82 secs, 1,463,762,192 bytes)

-- λ> length (mayoresMitad3 [1..4*10^3])

-- 2000

-- (0.02 secs, 0 bytes)

8 Comentarios

import Data.List

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad xs | even l    = aux (l `div` 2) xs
                | otherwise = aux (l `div` 2 + 1) xs
  where l = length xs

aux :: Ord a => Int -> [a] -> [a]
aux n xs | n > 0     = m : aux (n-1) (xs\\[m])
         | otherwise = []
  where m = maximum xs

import Data.List

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

mayoresMitad xs | even l = aux (l `div` 2) xs

| otherwise = aux (l `div` 2 + 1) xs

where l = length xs

aux :: Ord a => Int -> [a] -> [a]

aux n xs | n > 0 = m : aux (n-1) (xs\\[m])

| otherwise = []

where m = maximum xs

Responder

albcercid dice:

12-diciembre-2016 a las 20:29

Haskell

import Data.List (sort) mayoresMitad :: Ord a => [a] -> [a] mayoresMitad xs = drop p (sort xs) where p = length xs `div` 2

1
2
3
4
5

import Data.List (sort)

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad xs = drop p (sort xs)
where p = length xs `div` 2

Responder

import Data.List (sort)

-- 1ª Definición:
mayoresMitad1 :: Ord a =>  [a] -> [a]
mayoresMitad1 xs | xs == sort xs = drop minors xs
                 | otherwise     = drop minors (sort xs)
  where minors = div (length xs) 2

-- 2ª Definición:
mayoresMitad2 :: Ord a =>  [a] -> [a]
mayoresMitad2 xs = if xs == sort xs
                   then drop minors xs
                   else drop minors (sort xs)
  where minors = div (length xs) 2

-- 3ª Definición:
mayoresMitad3 :: Ord a => [a] -> [a]
mayoresMitad3 xs = dropWhile (<n) (sort xs)
  where n = sort xs !! div (length xs) 2

-- 4ª Definición:
mayoresMitad4 :: Ord a => [a] -> [a]
mayoresMitad4 xs = filter (>=n) xs
  where n = sort xs !! div (length xs) 2

import Data.List (sort)

-- 1ª Definición:

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

mayoresMitad1 xs | xs == sort xs = drop minors xs

| otherwise = drop minors (sort xs)

where minors = div (length xs) 2

-- 2ª Definición:

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

mayoresMitad2 xs = if xs == sort xs

then drop minors xs

else drop minors (sort xs)

where minors = div (length xs) 2

-- 3ª Definición:

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

mayoresMitad3 xs = dropWhile (<n) (sort xs)

where n = sort xs !! div (length xs) 2

-- 4ª Definición:

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

mayoresMitad4 xs = filter (>=n) xs

where n = sort xs !! div (length xs) 2

Responder

Mejor que ordenar ascendentemente es hacerlo descendentemente ya que la implementación perezosa no ordenará la mitad derecha y será un poco más rápida:

mayoresMitad :: Ord a =>[a] ->[a]
mayoresMitad xs = take ((length xs + 1) `div` 2) (sortBy (flip compare) xs)

1 2	mayoresMitad :: Ord a =>[a] ->[a] mayoresMitad xs = take ((length xs + 1) `div` 2) (sortBy (flip compare) xs)

Sin embargo, calcular el elemento k-ésimo de la lista ordenada (sin ordenarla) tiene coste lineal (aunque con constante multiplicativa muy alta por lo que es raramente usado). En este caso, para listas grandes obtener la media sale rentable frente a la pequeña constante multiplicativa de usar sort:

mayoresMitad''' :: Ord a =>[a] ->[a]
mayoresMitad''' xs = filter (>=m) xs where m = select ((length xs + 1) `div` 2) xs
-- usando la función `select` de: http://austinrochford.com/posts/2013-10-29-median-of-medians-in-haskell.html

mayoresMitad''' :: Ord a =>[a] ->[a]

mayoresMitad''' xs = filter (>=m) xs where m = select ((length xs + 1) `div` 2) xs

-- usando la función `select` de: http://austinrochford.com/posts/2013-10-29-median-of-medians-in-haskell.html

Para ver la ventaja la lista debe ser grande:

> xs <- mapM (const randomIO :: a -> IO Int) [1..10^7]
(20.78 secs, 20,562,977,088 bytes)
> sum xs
7959315391372911447
(3.65 secs, 735,164,824 bytes)
> sum $ mayoresMitad xs -- Usando sortBy
3548194200467751021
(46.62 secs, 9,877,335,720 bytes)
> sum $ mayoresMitad''' xs -- Usando `select`
3548194200467751021
(34.90 secs, 13,498,840,192 bytes)
>

> xs <- mapM (const randomIO :: a -> IO Int) [1..10^7]

(20.78 secs, 20,562,977,088 bytes)

> sum xs

7959315391372911447

(3.65 secs, 735,164,824 bytes)

> sum $ mayoresMitad xs -- Usando sortBy

3548194200467751021

(46.62 secs, 9,877,335,720 bytes)

> sum $ mayoresMitad''' xs -- Usando `select`

3548194200467751021

(34.90 secs, 13,498,840,192 bytes)

Responder

import Data.List

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad xs = drop (length xs `div` 2) (deMenorAMayor xs)

deMenorAMayor :: Ord a => [a] -> [a]
deMenorAMayor [] = []
deMenorAMayor[x] = [x]
deMenorAMayor (x:xs)
  | x < minimum xs = x : deMenorAMayor xs
  | otherwise      = minimum xs : deMenorAMayor (resto (x:xs))

resto :: Ord a => [a] -> [a]
resto [] = []
resto xs = [x | x <- xs, x /= minimum xs]

import Data.List

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

mayoresMitad xs = drop (length xs `div` 2) (deMenorAMayor xs)

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

deMenorAMayor [] = []

deMenorAMayor[x] = [x]

deMenorAMayor (x:xs)

| x < minimum xs = x : deMenorAMayor xs

| otherwise = minimum xs : deMenorAMayor (resto (x:xs))

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

resto [] = []

resto xs = [x | x <- xs, x /= minimum xs]

Responder

import Data.List

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad [] = []
mayoresMitad [x] = [x]
mayoresMitad xs = sort [x | x <- filter (> last ys) xs ] 
  where ys = take ((length xs) `div` 2) (sort xs)

import Data.List

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

mayoresMitad [] = []

mayoresMitad [x] = [x]

mayoresMitad xs = sort [x | x <- filter (> last ys) xs ]

where ys = take ((length xs) `div` 2) (sort xs)

Responder

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad xs = take n ys
  where ys = reverse (sort (nub xs))
        n | even long = long `div` 2
          | otherwise = 1 + (long `div` 2)
          where long = length ys

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

mayoresMitad xs = take n ys

where ys = reverse (sort (nub xs))

n | even long = long `div` 2

| otherwise = 1 + (long `div` 2)

where long = length ys

Responder

import Data.List

mayoresMitad :: Ord a => [a] -> [a]
mayoresMitad xs
  | (length xs) `mod` 2 /= 0 =
    take (((length xs) `div` 2) + 1) (reverse (sort xs))
  | otherwise =
    take ((length xs) `div` 2) (reverse (sort xs))

import Data.List

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

mayoresMitad xs

| (length xs) `mod` 2 /= 0 =

take (((length xs) `div` 2) + 1) (reverse (sort xs))

| otherwise =

take ((length xs) `div` 2) (reverse (sort xs))

Responder

Mayores que la mitad

Soluciones

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