Se dice que una sucesi\u00f3n x(1), …, x(n) est\u00e1 ordenada c\u00edclicamente si existe un \u00edndice i tal que la sucesi\u00f3n<\/p>\n
\n x(i), x(i+1), ..., x(n), x(1), ..., x(i-1)\n<\/pre>\nest\u00e1 ordenada crecientemente de forma estricta.<\/p>\n
Definir la funci\u00f3n<\/p>\n
\n ordenadaCiclicamente :: Ord a => [a] -> Maybe Int\n<\/pre>\ntal que (ordenadaCiclicamente xs)<\/code> es el \u00edndice a partir del cual est\u00e1 ordenada, si la lista est\u00e1 ordenado c\u00edclicamente y Nothing<\/code> en caso contrario. Por ejemplo,<\/p>\n\n ordenadaCiclicamente [1,2,3,4] == Just 0\n ordenadaCiclicamente [5,8,1,3] == Just 2\n ordenadaCiclicamente [4,6,7,5,1,3] == Nothing\n ordenadaCiclicamente [1,0,3,2] == Nothing\n ordenadaCiclicamente [1,2,0] == Just 2\n ordenadaCiclicamente \"cdeab\" == Just 3\n<\/pre>\nNota: Se supone que el argumento es una lista no vac\u00eda sin elementos repetidos.<\/p>\n
Soluciones<\/h4>\n\nmodule Ordenada_ciclicamente where\n\nimport Test.QuickCheck (Arbitrary, Gen, NonEmptyList (NonEmpty), Property,\n arbitrary, chooseInt, collect, quickCheck)\nimport Data.List (nub, sort)\nimport Data.Maybe (isJust, listToMaybe)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nordenadaCiclicamente1 :: Ord a => [a] -> Maybe Int\nordenadaCiclicamente1 xs = aux 0 xs\n where n = length xs\n aux i zs\n | i == n = Nothing\n | ordenada zs = Just i\n | otherwise = aux (i+1) (siguienteCiclo zs)\n\n-- (ordenada xs) se verifica si la lista xs est\u00e1 ordenada\n-- crecientemente. Por ejemplo,\n-- ordenada \"acd\" == True\n-- ordenada \"acdb\" == False\nordenada :: Ord a => [a] -> Bool\nordenada [] = True\nordenada (x:xs) = all (x <) xs && ordenada xs\n\n-- (siguienteCiclo xs) es la lista obtenida a\u00f1adiendo el primer elemento\n-- de xs al final del resto de xs. Por ejemplo,\n-- siguienteCiclo [3,2,5] => [2,5,3]\nsiguienteCiclo :: [a] -> [a]\nsiguienteCiclo [] = []\nsiguienteCiclo (x:xs) = xs ++ [x]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nordenadaCiclicamente2 :: Ord a => [a] -> Maybe Int\nordenadaCiclicamente2 xs =\n listToMaybe [n | n <- [0..length xs-1],\n ordenada (drop n xs ++ take n xs)]\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nordenadaCiclicamente3 :: Ord a => [a] -> Maybe Int\nordenadaCiclicamente3 xs\n | ordenada (bs ++ as) = Just k\n | otherwise = Nothing\n where (_,k) = minimum (zip xs [0..])\n (as,bs) = splitAt k xs\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_ordenadaCiclicamente1 :: NonEmptyList Int -> Bool\nprop_ordenadaCiclicamente1 (NonEmpty xs) =\n ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_ordenadaCiclicamente1\n-- +++ OK, passed 100 tests.\n\n-- La propiedad para analizar los casos de prueba\nprop_ordenadaCiclicamente2 :: NonEmptyList Int -> Property\nprop_ordenadaCiclicamente2 (NonEmpty xs) =\n collect (isJust (ordenadaCiclicamente1 xs)) $\n ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs\n\n-- El an\u00e1lisis es\n-- \u03bb> quickCheck prop_ordenadaCiclicamente2\n-- +++ OK, passed 100 tests:\n-- 89% False\n-- 11% True\n\n-- Tipo para generar listas\nnewtype Lista = L [Int]\n deriving Show\n\n-- Generador de listas.\nlistaArbitraria :: Gen Lista\nlistaArbitraria = do\n x <- arbitrary\n xs <- arbitrary\n let ys = x : xs\n k <- chooseInt (0, length ys)\n let (as,bs) = splitAt k (sort (nub ys))\n return (L (bs ++ as))\n\n-- Lista es una subclase de Arbitrary.\ninstance Arbitrary Lista where\n arbitrary = listaArbitraria\n\n-- La propiedad para analizar los casos de prueba\nprop_ordenadaCiclicamente3 :: Lista -> Property\nprop_ordenadaCiclicamente3 (L xs) =\n collect (isJust (ordenadaCiclicamente1 xs)) $\n ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs\n\n-- El an\u00e1lisis es\n-- \u03bb> quickCheck prop_ordenadaCiclicamente3\n-- +++ OK, passed 100 tests (100% True).\n\n-- Tipo para generar\nnewtype Lista2 = L2 [Int]\n deriving Show\n\n-- Generador de listas\nlistaArbitraria2 :: Gen Lista2\nlistaArbitraria2 = do\n x' <- arbitrary\n xs <- arbitrary\n let ys = x' : xs\n k <- chooseInt (0, length ys)\n let (as,bs) = splitAt k (sort (nub ys))\n n <- chooseInt (0,1)\n return (if even n\n then L2 (bs ++ as)\n else L2 ys)\n\n-- Lista es una subclase de Arbitrary.\ninstance Arbitrary Lista2 where\n arbitrary = listaArbitraria2\n\n-- La propiedad para analizar los casos de prueba\nprop_ordenadaCiclicamente4 :: Lista2 -> Property\nprop_ordenadaCiclicamente4 (L2 xs) =\n collect (isJust (ordenadaCiclicamente1 xs)) $\n ordenadaCiclicamente1 xs == ordenadaCiclicamente2 xs\n\n-- El an\u00e1lisis es\n-- \u03bb> quickCheck prop_ordenadaCiclicamente4\n-- +++ OK, passed 100 tests:\n-- 51% True\n-- 49% False\n\n-- La propiedad es\nprop_ordenadaCiclicamente :: Lista2 -> Bool\nprop_ordenadaCiclicamente (L2 xs) =\n all (== ordenadaCiclicamente1 xs)\n [ordenadaCiclicamente2 xs,\n ordenadaCiclicamente3 xs]\n\n-- La comprobaci\u00f3n es\n-- \u03bb> quickCheck prop_ordenadaCiclicamente\n-- +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n-- \u03bb> ordenadaCiclicamente1 ([100..4000] ++ [1..99])\n-- Just 3901\n-- (3.27 secs, 2,138,864,568 bytes)\n-- \u03bb> ordenadaCiclicamente2 ([100..4000] ++ [1..99])\n-- Just 3901\n-- (2.44 secs, 1,430,040,008 bytes)\n-- \u03bb> ordenadaCiclicamente3 ([100..4000] ++ [1..99])\n-- Just 3901\n-- (1.18 secs, 515,549,200 bytes)\n<\/pre>\nEl c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\nLa elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n