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