Menu Close

Ordenación valle

José A. Alonso,

La ordenación valle de la lista [79,35,54,19,35,25,12] es la lista [79,35,25,12,19,35,54] ya que es una permutación de la primera y cumple las siguientes condiciones

  • se compone de una parte decreciente ([79,35,25]), un elemento mínimo (12) y una parte creciente ([19,35,54]);
  • las dos partes tienen el mismo número de elementos;
  • cada elemento de la primera parte es mayor o igual que su correspondiente en la segunda parte; es decir. 79 ≥ 54, 35 ≥ 35 y 25 ≥ 19;
  • además, la diferencia entre dichos elementos es la menor posible.

En el caso, de que la longitud de la lista sea par, la división tiene sólo dos partes (sin diferenciar el menor elemento). Por ejemplo, el valle de [79,35,54,19,35,25] es [79,35,25,19,35,54].

Definir la función

   valle :: [Int] -> [Int]

tal que (valle xs) es la ordenación valle de la lista xs. Por ejemplo,

   valle [79,35,54,19,35,25,12]       ==  [79,35,25,12,19,35,54]
   valle [79,35,54,19,35,25]          ==  [79,35,25,19,35,54]
   valle [67,93,100,-16,65,97,92]     ==  [100,93,67,-16,65,92,97]
   valle [14,14,14,14,7,14]           ==  [14,14,14,7,14,14]
   valle [14,14,14,14,14]             ==  [14,14,14,14,14]
   valle [17,17,15,14,8,7,7,5,4,4,1]  ==  [17,15,8,7,4,1,4,5,7,14,17]

En el último ejemplo se muestra cómo la última condición descarta la posibilidad de que la lista [17,17,15,14,8,1,4,4,5,7,7] también sea solución ya que aunque se cumplen se cumplen las tres primeras condiciones la diferencia entre los elementos correspondientes es mayor que en la solución; por ejemplo, 17 – 7 > 17 – 17.

Soluciones

import Data.List (sort, sortBy)
 
-- 1ª solución
valle1 :: [Int] -> [Int]
valle1 xs = ys ++ reverse zs
  where (ys,zs) = aux (reverse (sort xs))
        aux []       = ([],[])
        aux [x]      = ([x],[])
        aux [x,y]    = ([x,y],[])
        aux (x:y:zs) = (x:as,y:bs)
          where (as,bs) = aux zs
 
-- 2ª solución
valle2 :: [Int] -> [Int]
valle2 = aux . reverse . sort
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]
 
-- 3ª solución
valle3 :: [Int] -> [Int]
valle3 = aux . sortBy (flip compare)
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]
 
-- Comparación de eficiencia
-- =========================
 
-- λ> length (valle1 [1..2*10^4])
-- 20000
-- (0.02 secs, 8,621,240 bytes)
-- λ> length (valle2 [1..2*10^4])
-- 20000
-- (2.68 secs, 8,595,637,880 bytes)
-- λ> length (valle3 [1..2*10^4])
-- 20000
-- (2.67 secs, 8,594,678,104 bytes)
Medio
, , , , , ,

9 soluciones de “Ordenación valle”

  1. Responder
    alerodrod5 
    import Data.List (delete)
 
valle :: [Int] -> [Int]
valle xs
  | even (length xs) = parteDecreciente xs ++ parteCreciente xs
  | otherwise        = parteDecreciente xs ++ (minimum xs:parteCreciente xs)
 
listaOrdenada :: [Int] -> [Int]
listaOrdenada xs
  | even (length xs) = sort xs
  | otherwise        = sort (delete (minimum xs) xs) 
 
parteDecreciente :: [Int] -> [Int]
parteDecreciente xs =
  reverse [x | (x,y) <- zip (listaOrdenada xs) [1..], even y]
 
parteCreciente :: [Int] -> [Int]
parteCreciente xs =
  [x | (x,y) <- zip (listaOrdenada xs) [1..], odd y]
  2. Responder
    jorcatote 
    import Data.List (sort)
 
valle :: [Int] -> [Int]
valle xs = aux [] [] $ (reverse . sort) xs
  where aux a b (x:y:xs) = aux (x:a) (y:b) xs
        aux a b xs       = reverse a ++ xs ++ b
  3. Responder
    luicedval 
    import Data.List (sort)
 
valle :: [Int] -> [Int]
valle xs =
  parteDecreciente xs ++ parteCreciente xs
 
parteCreciente :: [Int] -> [Int]
parteCreciente xs =
  reverse [x | (x,y) <- zip (reverse . sort $ xs) [1..], even y]
 
parteDecreciente :: [Int] -> [Int]
parteDecreciente xs
  | odd (length xs) = reverse [x | (x,y) <- zip (sort xs) [1..], odd y]
  | otherwise       = [x | (x,y) <- zip (reverse . sort $ xs) [1..], odd y]
  4. Responder
    mirmednav 
    import Data.List (sortBy)
 
valle :: [Int] -> [Int]
valle xs = aux [] $ sortBy (flip compare) xs
  where aux ys (x:y:xs) = x : aux (y:ys) xs
        aux ys xs       = xs ++ ys
  5. Responder
    angruicam1 
    import Data.List (sort)
import Data.List.Split (divvy)
 
valle :: [Int] -> [Int]
valle xs = concat . divvy 1 2 $ reverse ys ++ ys
  where ys = sort xs
  6. Responder
    luicedval 
    import Data.List 
 
valle :: [Int] -> [Int]
valle xs = lista (reverse . sort $ xs)
 
lista :: [Int] -> [Int]
lista []       = []
lista (x:[])   = [x]
lista (x:y:xs) = x : lista xs ++ [y]
  7. Responder
    antnavoro 
    import Data.List (sort)
 
valle :: [Int] -> [Int]
valle = aux . reverse . sort
  where aux []       = []
        aux [x]      = [x]
        aux (x:y:xs) = x : aux xs ++ [y]
    • Responder
      antnavoro 
      import Data.List (sort)
 
valle :: [Int] -> [Int]
valle = aux1 . reverse . sort
  where aux1 (x:y:xs) = x : aux1 xs ++ [y]
        aux1 xs       = xs
  8. Responder
    anaagumun1 
    import Data.List (sort)
valle :: [Int] -> [Int]
valle xs = concat $ aux xs
  where aux xs = [[x | (x,y) <- h, even y], reverse [z | (z,k) <- h, odd k]]
        h = zip (reverse (sort xs)) [0..]

Escribe tu solución

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