Ordenada cíclicamente
Se dice que una sucesión x(1), …, x(n) está ordenada cíclicamente si existe un índice i tal que la sucesión
|
1 |
x(i), x(i+1), ..., x(n), x(1), ..., x(i-1) |
está ordenada crecientemente de forma estricta.
Definir la función
|
1 |
ordenadaCiclicamente :: Ord a => [a] -> Maybe Int |
tal que (ordenadaCiclicamente xs) es el índice a partir del cual está ordenada, si la lista está ordenado cíclicamente y Nothing en caso contrario. Por ejemplo,
|
1 2 3 4 5 6 |
ordenadaCiclicamente [1,2,3,4] == Just 0 ordenadaCiclicamente [5,8,1,3] == Just 2 ordenadaCiclicamente [4,6,7,5,1,3] == Nothing ordenadaCiclicamente [1,0,3,2] == Nothing ordenadaCiclicamente [1,2,0] == Just 2 ordenadaCiclicamente "cdeab" == Just 3 |
Nota: Se supone que el argumento es una lista no vacía sin elementos repetidos.
Soluciones
|
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 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 |
module Ordenada_ciclicamente where import Test.QuickCheck (Arbitrary, Gen, NonEmptyList (NonEmpty), Property, arbitrary, chooseInt, collect, quickCheck) import Data.List (nub, sort) import Data.Maybe (isJust, listToMaybe) -- 1ª solución -- =========== ordenadaCiclicamente1 :: Ord a => [a] -> Maybe Int ordenadaCiclicamente1 xs = aux 0 xs where n = length xs aux i zs | i == n = Nothing | ordenada zs = Just i | otherwise = aux (i+1) (siguienteCiclo zs) -- (ordenada xs) se verifica si la lista xs está ordenada -- crecientemente. Por ejemplo, -- ordenada "acd" == True -- ordenada "acdb" == False ordenada :: Ord a => [a] -> Bool ordenada [] = True ordenada (x:xs) = all (x <) xs && ordenada xs -- (siguienteCiclo xs) es la lista obtenida añadiendo el primer elemento -- de xs al final del resto de xs. Por ejemplo, -- siguienteCiclo [3,2,5] => [2,5,3] siguienteCiclo :: [a] -> [a] siguienteCiclo [] = [] siguienteCiclo (x:xs) = xs ++ [x] -- 2ª solución -- =========== ordenadaCiclicamente2 :: Ord a => [a] -> Maybe Int ordenadaCiclicamente2 xs = listToMaybe [n | n <- [0..length xs-1], ordenada (drop n xs ++ take n xs)] -- 3ª solución -- =========== ordenadaCiclicamente3 :: Ord a => [a] -> Maybe Int ordenadaCiclicamente3 xs | ordenada (bs ++ as) = Just k | otherwise = Nothing where (_,k) = minimum (zip xs [0..]) (as,bs) = splitAt k xs -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_ordenadaCiclicamente1 :: NonEmptyList Int -> Bool prop_ordenadaCiclicamente1 (NonEmpty xs) = ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs -- La comprobación es -- λ> quickCheck prop_ordenadaCiclicamente1 -- +++ OK, passed 100 tests. -- La propiedad para analizar los casos de prueba prop_ordenadaCiclicamente2 :: NonEmptyList Int -> Property prop_ordenadaCiclicamente2 (NonEmpty xs) = collect (isJust (ordenadaCiclicamente1 xs)) $ ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs -- El análisis es -- λ> quickCheck prop_ordenadaCiclicamente2 -- +++ OK, passed 100 tests: -- 89% False -- 11% True -- Tipo para generar listas newtype Lista = L [Int] deriving Show -- Generador de listas. listaArbitraria :: Gen Lista listaArbitraria = do x <- arbitrary xs <- arbitrary let ys = x : xs k <- chooseInt (0, length ys) let (as,bs) = splitAt k (sort (nub ys)) return (L (bs ++ as)) -- Lista es una subclase de Arbitrary. instance Arbitrary Lista where arbitrary = listaArbitraria -- La propiedad para analizar los casos de prueba prop_ordenadaCiclicamente3 :: Lista -> Property prop_ordenadaCiclicamente3 (L xs) = collect (isJust (ordenadaCiclicamente1 xs)) $ ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs -- El análisis es -- λ> quickCheck prop_ordenadaCiclicamente3 -- +++ OK, passed 100 tests (100% True). -- Tipo para generar newtype Lista2 = L2 [Int] deriving Show -- Generador de listas listaArbitraria2 :: Gen Lista2 listaArbitraria2 = do x' <- arbitrary xs <- arbitrary let ys = x' : xs k <- chooseInt (0, length ys) let (as,bs) = splitAt k (sort (nub ys)) n <- chooseInt (0,1) return (if even n then L2 (bs ++ as) else L2 ys) -- Lista es una subclase de Arbitrary. instance Arbitrary Lista2 where arbitrary = listaArbitraria2 -- La propiedad para analizar los casos de prueba prop_ordenadaCiclicamente4 :: Lista2 -> Property prop_ordenadaCiclicamente4 (L2 xs) = collect (isJust (ordenadaCiclicamente1 xs)) $ ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs -- El análisis es -- λ> quickCheck prop_ordenadaCiclicamente4 -- +++ OK, passed 100 tests: -- 51% True -- 49% False -- La propiedad es prop_ordenadaCiclicamente :: Lista2 -> Bool prop_ordenadaCiclicamente (L2 xs) = all (== ordenadaCiclicamente1 xs) [ordenadaCiclicamente2 xs, ordenadaCiclicamente3 xs] -- La comprobación es -- λ> quickCheck prop_ordenadaCiclicamente -- +++ OK, passed 100 tests. -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> ordenadaCiclicamente1 ([100..4000] ++ [1..99]) -- Just 3901 -- (3.27 secs, 2,138,864,568 bytes) -- λ> ordenadaCiclicamente2 ([100..4000] ++ [1..99]) -- Just 3901 -- (2.44 secs, 1,430,040,008 bytes) -- λ> ordenadaCiclicamente3 ([100..4000] ++ [1..99]) -- Just 3901 -- (1.18 secs, 515,549,200 bytes) |
El código se encuentra en GitHub.
La elaboración de las soluciones se describe en el siguiente vídeo
Nuevas soluciones
- En los comentarios se pueden escribir nuevas soluciones.
- El código se debe escribir entre una línea con <pre lang="haskell"> y otra con </pre>