Elementos que respetan la ordenación

5 Comentarios

1. Haskell

   import Data.List import Test.QuickCheck respetuosos :: Ord a => [a] -> [a] respetuosos xs = [ x | (x,ys,zs) <- zip3 xs (inits xs) (tails xs) , all (<=x) ys , all (>=x) zs ] prop_respetuosos1 :: [Int] -> Bool prop_respetuosos1 xs = respetuosos ys == ys where ys = sort xs prop_respetuosos2 :: [Int] -> Bool prop_respetuosos2 xs = length (respetuosos ys) <= 1 where ys = nub (reverse (sort xs))

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   import Data.List import Test.QuickCheck   respetuosos :: Ord a => [a] -> [a] respetuosos xs = [ x | (x,ys,zs) <- zip3 xs (inits xs) (tails xs)                      , all (<=x) ys                      , all (>=x) zs ]   prop_respetuosos1 :: [Int] -> Bool prop_respetuosos1 xs = respetuosos ys == ys   where ys = sort xs   prop_respetuosos2 :: [Int] -> Bool prop_respetuosos2 xs = length (respetuosos ys) <= 1   where ys = nub (reverse (sort xs))

   Responder

2. Haskell

   {- Se pide devolver aquellos elementos que cumplan que: - los elementos a su izq son menores o iguales - los elementos a su der son mayores o iguales Ésto es lo mismo que decir que cualquier elemento debe estar acotado (comprendido) entre la función máximo acumulado por la izquierda y la función mínimo acumulado por la derecha (ambas monótonas). Quizás se ve mejor si consideramos los cuatro cuadrantes centrados en él y hacemos mover la gráfica a izq o der: : ######### : ##### : ## ··················#X··················· ### : ####### : __######___________:___________________ Así, podemos obtener los respetuosos con coste lineal. -} respetuosos :: Ord a =>[a] ->[a] respetuosos xs = [x | (a, x, b) <-zip3 (scanl1 max xs) xs (scanr1 min xs), a <= x && x <= b] {- Que todos los elementos de `sort` son respetuosos parece obvio. Que en `nub . reverse . sort` hay a lo sumo uno se ve fácilmente con la gráfica anterior pues, siempre que en la lista resultante haya más de un elemento no habrá respetuosos al caer todos ellos en el 2º y 4º cuadrantes. Así, una propiedad más fuerte podrían ser que `(nub . reverse . sort) xs` tendrá un respetuoso sii `(length . nub) xs == 1` y 0 en otro caso. -} prop_reverse_sort xs = (not . null) xs ==> case ((length . nub) xs, (length . respetuosos . nub . reverse . sort) xs) of (1, 1) ->True (_, 0) ->True _ ->False

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43

   {-   Se pide devolver aquellos elementos que cumplan que:       - los elementos a su izq son menores o iguales     - los elementos a su der son mayores o iguales     Ésto es lo mismo que decir que cualquier elemento debe   estar acotado (comprendido) entre la función máximo   acumulado por la izquierda y la función mínimo acumulado   por la derecha (ambas monótonas).     Quizás se ve mejor si consideramos los cuatro cuadrantes   centrados en él y hacemos mover la gráfica a izq o der:                          :        #########                        :   #####                        : ##     ··················#X···················                    ### :             #######    :     __######___________:___________________     Así, podemos obtener los respetuosos con coste lineal. -} respetuosos :: Ord a =>[a] ->[a] respetuosos xs = [x | (a, x, b) <-zip3 (scanl1 max xs) xs (scanr1 min xs), a <= x && x <= b]   {-   Que todos los elementos de `sort` son respetuosos parece obvio.     Que en `nub . reverse . sort` hay a lo sumo uno se ve fácilmente   con la gráfica anterior pues, siempre que en la lista resultante haya   más de un elemento no habrá respetuosos al caer todos ellos en el 2º y   4º cuadrantes.     Así, una propiedad más fuerte podrían ser que `(nub . reverse . sort) xs`   tendrá un respetuoso sii `(length . nub) xs == 1` y 0 en otro caso. -} prop_reverse_sort xs = (not . null) xs ==>   case ((length . nub) xs, (length . respetuosos . nub . reverse . sort) xs) of     (1, 1) ->True     (_, 0) ->True     _      ->False

   Responder

   1. De hecho, dado que en una posición sólo hay un único elemento, cuando se cumple la condición el mínimo y el máximo coinciden luego puede simplificarse (aunque apenas hay optimización) a:

      Haskell

      respetuosos xs = [a | (a, b) <-zip (scanl1 max xs) (scanr1 min xs), a == b]

      1	respetuosos xs = [a | (a, b) <-zip (scanl1 max xs) (scanr1 min xs), a == b]

      Responder

3. respetuosos :: Ord a => [a] -> [a] respetuosos xs = reverse $ aux [] [] xs where aux v y [] = v aux v y (x:xs) | ny y && nx xs = aux (x:v) (x:y) xs | ny y && mx xs >= x = aux (x:v) (x:y) xs | ny y = aux v (x:y) xs | nx xs && x >= my y = aux (x:v) (x:y) xs | nx xs = aux v (x:y) xs | x >= my y && mx xs >= x = aux (x:v) (x:y) xs | otherwise = aux v (x:y) xs ny y = null y nx xs = null xs mx xs = minimum xs my y = maximum y prop_respetuosos :: Ord a => [a] -> Bool prop_respetuosos xs = sort xs == respetuosos (sort xs) -- λ> quickCheck prop_respetuosos -- +++ OK, passed 100 tests. prop_respetuosos2 :: Ord a => [a] -> Bool prop_respetuosos2 xs = 1 >= length (nub (reverse (sort xs))) -- quickCheck prop_respetuosos2 -- +++ OK, passed 100 tests.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   respetuosos :: Ord a => [a] -> [a] respetuosos xs = reverse $ aux [] [] xs   where aux v y [] = v         aux v y (x:xs) | ny y && nx xs           = aux (x:v) (x:y) xs                        | ny y && mx xs >= x      = aux (x:v) (x:y) xs                        | ny y                    = aux v (x:y) xs                        | nx xs &&  x >= my y     = aux (x:v) (x:y) xs                        | nx xs                   = aux v (x:y) xs                        | x >= my y && mx xs >= x = aux (x:v) (x:y) xs                            | otherwise               = aux v (x:y) xs         ny y  = null y         nx xs = null xs         mx xs = minimum xs         my y  = maximum y   prop_respetuosos :: Ord a => [a] -> Bool prop_respetuosos xs = sort xs == respetuosos (sort xs)   --    λ> quickCheck prop_respetuosos --    +++ OK, passed 100 tests.   prop_respetuosos2 :: Ord a => [a] -> Bool prop_respetuosos2 xs = 1 >= length (nub (reverse (sort xs)))   --    quickCheck prop_respetuosos2 --    +++ OK, passed 100 tests.

   Responder

4. Haskell

   respetuosos :: Ord a => [a] -> [a] respetuosos ns = reverse $ aux (reverse ns) where aux [] = [] aux (x:xs) | x == maxi = x : aux xs | otherwise = aux $ tail $ dropWhile (/= maximum xs) xs where maxi = maximum (x:xs) prop_resp1 :: Ord a => [a] -> Bool prop_resp1 xs = respetuosos (sort xs) == xs -- *Main> quickCheck prop_resp1 -- +++ OK, passed 100 tests. prop_resp2 :: Ord a => [a] -> Bool prop_resp2 xs = length (respetuosos (nub (reverse (sort xs)))) <= 1 -- *Main> quickCheck prop_resp2 -- +++ OK, passed 100 tests.

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

   respetuosos :: Ord a => [a] -> [a] respetuosos ns = reverse $ aux (reverse ns)   where     aux [] = []     aux (x:xs) | x == maxi = x : aux xs                | otherwise = aux $ tail $ dropWhile (/= maximum xs) xs       where maxi = maximum (x:xs)   prop_resp1 :: Ord a => [a] -> Bool prop_resp1 xs = respetuosos (sort xs) == xs   -- *Main> quickCheck prop_resp1 -- +++ OK, passed 100 tests.   prop_resp2 :: Ord a => [a] -> Bool prop_resp2 xs = length (respetuosos (nub (reverse (sort xs)))) <= 1   -- *Main> quickCheck prop_resp2 -- +++ OK, passed 100 tests.

   Responder